I posted on When did Math get so hard? a commenter pointed out that one can also ask
When did Computer Science Theory Get so Hard?
For the Math-question I could only speculate. For CS- I WAS THERE! When I was in Grad School one could learn all of Complexity theory in a year-long course (a hard one, but still!). The main tools were logic and combinatorics. No Fourier Transforms over finite fields. I am NOT going to say
Those were the good old days.
I will say that it was easier to make a contribution without knowing much. Oddly enough, it is MORE common for ugrads and grad students to publish NOW then it was THEN, so that may be a pair of ducks.
Random Thoughts on This Question
1) The Graph Minor Theorem was when P lost its innocence. Before the GMT most (though not all) problems in P had easy-to-understand algorithms using algorithmic paradigms (e.g., Dynamic Programming) and maybe some combinatorics. Computational Number Theory used.... Number Theory (duh), but I don't think it was hard number theory. One exception was Miller's Primality test which needed to assume the Extended Riemann Hypothesis- but you didn't have to understand ERH to use it.
1.5) GMT again. This did not only give hard-deep-math algorithms to get problems in P. It also pointed to how hard proving P NE NP would be--- to rule out something like a GMT-type result to get SAT in P seems rather hard.
2) Oracle Constructions were fairly easy diagonalizations. It was bummed out that I never had to use an infinite injury priority argument. That is, I knew some complicated recursion theory, but it was never used.
2.5) Oracles again. Dana Angluin had a paper which used some complicated combinatorics to construct an oracle, see here. Later Andy Yao showed that there is an oracle A such that PH^A NE PSPACE^A. You might know that result better as
Constant depth circuits for parity must have exponential size.
I think we now care about circuits more than oracles, see my post here about that issue. Anyway, oracle results since then have used hard combinatorial and other math arguments.
3) The PCP result was a leap forward for difficulty. I don't know which paper to pick as THE Leap since there were several. And papers after that were also rather difficult.
4) I had a blog post here where I asked if REDUCTIONS ever use hard math. Some of the comments are relevant here:
Stella Biderman: The deepest part of the original PCP theorem is the invention of the VC paradigm in the 1990's.
Eldar: Fourier Theory was introduced to CS with Hastad's Optimal Approximation results. Today it might not be considered deep, but I recall when it was.
Also there are Algebraic Geometry codes which use downright arcane mathematics...
Hermann Gruber refers to Comp Topology and Comp Geometry and points to the result that 3-manifold knot genus is NP-complete, see here.
Anonymous (they leave many comments) points to the deep math reductions in arithmetic versions of P/NP classes, and Mulmuley's work (Geometric Complexity Theory).
Timothy Chow points out that `deep' could mean several things and points to a math overflow post on the issue of depth, here.
Marzio De Biasi points out that even back in 1978 there was a poly reduction that required a good amount of number theory: the NPC of the Diophantine binary quad equation
ax^2 + by + c = 0
by Manders and Adelman, see here.
(Bill Comment) I tend to think this is an outlier- for the most part, CS theory back in the 1970's did not hard math.
4) Private Info Retrieval (PIR). k databases each have the same n-bit string and cannot talk to each other. a server wants the ith bit and (in the info-theoretic case) wants the DBs to know NOTHING about the question i.
Easy results (to understand) 2-server, n^{1/3}. here.
Hard results: 2-server n^{O(\sqrt{loglogn/log n)}, here.
(I have a website on PIR, not maintained, here.)
5) Babai's algorithm for GI in quasi-poly time used hard math.
6) If I knew more CS theory I am sure I would have more papers listed.
But now its your turn:
When did you realize Gee, CS theory is harder than (a) you thought, (b) it used to be.
@gasarch: touching on just one of the points -- publications
ReplyDelete(in case that's a metric to evaluate output and thus
a correlation to hardness.)
My own myopic perception is that getting things published at u/grad level is simply a result of
* new mini frontiers being pioneered/proposed
* low hanging fruits have been picked and analyzed;
in the past the focus used to be on more abstract/general solutions
* many new journals/conferences popped up
(and sadly, quality varies vastly)
* we actually have a mature ecosystem with many professors needing to publish work; thus easier for u/grads to make mini contributions (or, as we all know, sometimes quite the opposite in terms of contribution -- w/ sad endings.)
So, I presume the rate/number of publications should not be used as metric for hardness.
Hmm, it is easy to say that people are plucking low hanging fruit. This is what the current generation thinks about the past work because problems were easier then and there were fewer people. The field has gotten deeper and broader and there are many more people working in it. The math may nor may not be hard but each area requires domain knowledge to understand and make progress. That's it.
DeleteI'm supposed to say, "When I read _The Golden Ticket_, right :-)?
ReplyDeleteI'm an engineer, not a theorist, and I'm...not old, but getting there. The very little I knew about theory I learned from Carver Mead, Richard Feynman, TAOCP, and eventually a battered copy of the 1979 Hopcroft and Ullman automata & compilers book. Oh, and I read a few things like the original Karp and Turing papers. My "home" conferences would be places like ASPLOS, ISCA, SIGCOMM, USENIX ATC, not STOC and FOCS. So it should not have been but was something of a surprise to me to discover that, while I was busy with other things, the theorists were...working. And discovering new things.
In 2003, I dropped the classical gig and started working on quantum computing full time, more or less (most of my teaching is still classical systems, and I work closely with Internet operations and education people). Today, my gig is still systems, it's just quantum instead of classical systems. I do a lot of work on Quantum Internet, machine-specific compilation of algorithms, architecture, quantum error correction; just a bit on algorithms themselves, and recently a little on cryptography. So I need to know more theory, but I spend more time reading quantum hardware and quantum algorithms papers.
When I cracked open Mike & Ike (Nielsen & Chuang) and discovered that were was going to be more than a single quantum complexity class wedged in between(?) P and NP, I thought, "Hmm, I have some studying to do."
That amount of studying looked tractable until I discovered the Complexity Zoo.
One needs to qualify for whom cs-theory got harder. It may be harder for a rusty cs-researcher to contribute high quality work or to get familiar with the new techniques. For a mathematician well versed in the relevant topic it used to be and still is a relatively easy prey. But and therefore, success in cs-theory is not particularly prestigious in math. I think logic and cs-theory (in earlier times cs-theory looked like a subfield of logic) still rank at the bottom of the math internal ranking of fields. The only Fields Medal for logic was awarded in 1966 (to Paul Cohen for resolving CH). For cs-theory none was awarded so far and we may not live to see when someone eventually resolves P-NP earning the first Fields Medal for cs-theory. Probably this will be a mathematician proper rather than someone raised as a computer scientist :-)
ReplyDeleteThis is just bragging with no meaning. Who cares really about these rankings etc? Everyone wants to distinguish themselves so mathematicians may want to brag about their depth, CS people about their salaries, or what ever. Difficulty is not the point in life.
DeleteThe distinction between a mathematician and a theoretical computer scientist is very thin or perhaps non-existent.
ReplyDeleteNote that Field medal winners Gowers and Tao have an interest in P vs NP though I am unaware of any papers they may have on it.
The true mathematician who resolving the Poincaré conjecture would think that the CS theory just likes an exercise listed in the textbook.
ReplyDeleteThere are brilliant people in both math and CS. There are conjectures in Math that were solved by people in CS and vice-versa.
DeleteThere are times when Math ends up applying to CS or Physics or ...
There are times when CS ends up applying to Math or Phyics or
There are times when Physics ...
There are times when X ends up applying to Y
None of these fields has a moral or intellectual superiority to any other field.
I have meant to do a blog post about times when a CS result was used to resolve a math conjecture. Your comment has inspired me to actually do such a post. Thank you.