Complexity theory has changed over the years.
How to really track these things?
One way is to look at the list of topics on the
Call For papers for the
CCC conference (called STRUCTURES until the name changed, another sign of change).
Below I include pointers to the call for papers from
1986, 1997, and 2008. I also include the list of topics
and I comment on them.

The 1986 CCC (then called STRUCTURES)
call for
papers (third page is best view)
had this list:

Structure of Complexity Classes. (What does this even mean?)

Properties of NPcomplete sets.

Relations between Complexity Classes. (I wish we had more.)

Resourcebounded Reducibilities.

Theory of Relativizations. (I think this means oracles.)

Recursion Theoretic Aspects. (To general.)

Kolmogorov complexity and randomness.

Cryptocomplexity.

Applications of Finite Model Theory.

Independence Results. (I wish we had more.)

The 1997 CCC
call for
papers
had this list:

Structure of Complexity Classes. (I still do not know what this means.)

Resourcebounded Reducibilities.

Interactive Proof Systems.

Computational Randomness.

Circuits and other Concrete Computational Models.

Proof Complexity

Communication Complexity.

Theory of Relativizations. (I'm surprised this is still here.)

Complexity and Logic. (To general.)

Kolmogorov complexity.

Cryptographic complexity. (Is this different from Cryptocomplexity?)

Complexity and Learning. (Has there ever been a paper on this at CCC?)
(ADDED LATER Rocco found quite a few and then I generated a list which
I am sure is incomplete
here.

The 2008
call for papers
had this list:

Structure of Complexity Classes (Do they keep this topic for traditions sake?)

Reducibilities and Completeness.

Proof Complexity.

Interactive and Probabilistic Proof Systems.

Inapproximability. (I'm surprised this wasn't on the 1997 list.)

Complexity in other Concrete Computational Models. (Other than what?)

Kolmogorov complexity.

Quantum Complexity. (Not sure when it first entered the list, though it was on the 2002 CFP.)

Circuits Complexity.

Communication Complexity.

Complexity and Logic. (Too general.)

Pseudorandomness and derandomization. (How does this differ from Computational Randomness?)

Average case complexity. (I'm surprised it was not on the 1997 list.)

Complexity and Learning. (What is this still doing on the list?)

Cryptographic complexity.
NOTES:

The only topics on all three lists:
Reducibilities, Kolmogorov Complexity,
Cryptographic complexity. Maybe randomness.
Depending on how you count `Logic and Complexity'
maybe finite model theory.

I was surprised there was NOTHING on concrete models
of complexity in 1986. FurstSaxeSipser was already
known (1981 FOCS, 1984 MST) so I would think Circuits
would be of interest. Realize that FSS was first presented
as an attempt
to get an oracle that separates PH from PSPACE
(which later succeeded Yao and Hastad).
You can feel the paradigm shifting and circuits becoming
important unto themselves as opposed to servicing
recursiontheoretic complexity.

Perhaps I shouldn't be surprised the list of topics may lag
behind the reality. It takes a few years to catch up.

The numberoftopics has grown from 10 to 12 to 15.
At this rate...

The change to the topics seems to have come WITHOUT an old guard
resisting the change. Why was this? TCS is young enough that people
could change fields? TCS is young enough to not have an old guard?
I always thought that "structure of complexity classes" referred to things like Ladner's theorem or the BermanHartmanis isomorphism conjecture, i.e., properties of a complexity class beyond its mere existence as an arbitrary set of strings.
ReplyDeleteTo answer one of Bill's questions, there have been at least a halfdozen papers on complexity and learning at CCC in the past decade.
ReplyDeleteI searched for the string "learn" in the CCC proceedings tables of contents going back to 2001. There were papers whose titles include the term "learning" or "learnability" in 2001, 2002, 2005, 2006, 2008, 2009 and 2010, including Oded Regev's invited talk and survey paper on "The Learning with Errors Problem" in 2010.
I imagine that looking beyond just paper titles would turn up additional CCC papers that are
related to learning.
 Rocco
FYI: There was a nice article on TCS in last week's New Yorker! Check it out: http://www.newyorker.com/reporting/2011/05/02/110502fa_fact_galchen
ReplyDelete(subscription required)
Rocco THANKS, you inspired me to look in to this and I added to the post a pointer to a list of all learning theory in CCC papers I could find.
ReplyDeleteIt is interesting that the terms "sampling", "validation", and "verification" appear in none of the lists ... and yet in practice, these three are among the most ubiquitous, most difficult, and most interrelated computational challenges that we face.
ReplyDeleteBill,
ReplyDeleteYou showed the 2008 list in columnmajor order. In writing out the revisions of the 2007 list from the PC, I assumed that it would be read in rowmajor order. In that case, "other concrete computational models" would be read after "circuit complexity" and "communication complexity". (BTW: This did not represent order of importance at all.)
"Computational Randomoness" and "Kolmogorov complexity" seemed to have too much overlap so the PC chose to make the split clearer.
Yes. It was tradition to keep the first topic and the sense in Timothy Chow's comment seems correct: As I understand it, it refers to how the entire web of complexity classes gives a structure within which we can classify computational problems. This includes containments, collapses, reducibility, etc and may be expressed as in the complexity zoo diagram.
When "Structures" started in 1986, the "concrete" side of complexity was very well represented in STOC/FOCS (Barrington's simulation of NC^1 by constant width BPs and Hastad's parity lower bound were among the highlights of that year's STOC) but other aspects of complexity were not and those were emphasized in the call. It was clearly a mistake and some of the papers at the first Structures were definitely "concrete". (e.g., James Lynch's paper on AC^0 lower bounds for small cliques was at the first one and Kalyanasundaram and Schnitger's original randomized CC lower bounds for disjointness were at the second.)