Thursday, May 05, 2011

How has the STRUCTURES, OH- I mean CCC Conference changed: Lets look at the Call For Papers

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.

  1. The 1986 CCC (then called STRUCTURES) call for papers (third page is best view) had this list:
    1. Structure of Complexity Classes. (What does this even mean?)
    2. Properties of NP-complete sets.
    3. Relations between Complexity Classes. (I wish we had more.)
    4. Resource-bounded Reducibilities.
    5. Theory of Relativizations. (I think this means oracles.)
    6. Recursion Theoretic Aspects. (To general.)
    7. Kolmogorov complexity and randomness.
    8. Crypto-complexity.
    9. Applications of Finite Model Theory.
    10. Independence Results. (I wish we had more.)
  2. The 1997 CCC call for papers had this list:
    1. Structure of Complexity Classes. (I still do not know what this means.)
    2. Resource-bounded Reducibilities.
    3. Interactive Proof Systems.
    4. Computational Randomness.
    5. Circuits and other Concrete Computational Models.
    6. Proof Complexity
    7. Communication Complexity.
    8. Theory of Relativizations. (I'm surprised this is still here.)
    9. Complexity and Logic. (To general.)
    10. Kolmogorov complexity.
    11. Cryptographic complexity. (Is this different from Crypto-complexity?)
    12. 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.
  3. The 2008 call for papers had this list:
    1. Structure of Complexity Classes (Do they keep this topic for traditions sake?)
    2. Reducibilities and Completeness.
    3. Proof Complexity.
    4. Interactive and Probabilistic Proof Systems.
    5. Inapproximability. (I'm surprised this wasn't on the 1997 list.)
    6. Complexity in other Concrete Computational Models. (Other than what?)
    7. Kolmogorov complexity.
    8. Quantum Complexity. (Not sure when it first entered the list, though it was on the 2002 CFP.)
    9. Circuits Complexity.
    10. Communication Complexity.
    11. Complexity and Logic. (Too general.)
    12. Pseudorandomness and derandomization. (How does this differ from Computational Randomness?)
    13. Average case complexity. (I'm surprised it was not on the 1997 list.)
    14. Complexity and Learning. (What is this still doing on the list?)
    15. Cryptographic complexity.
NOTES:
  1. 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.
  2. I was surprised there was NOTHING on concrete models of complexity in 1986. Furst-Saxe-Sipser 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 recursion-theoretic complexity.
  3. Perhaps I shouldn't be surprised- the list of topics may lag behind the reality. It takes a few years to catch up.
  4. The number-of-topics has grown from 10 to 12 to 15. At this rate...
  5. 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?
Posted by at

6 comments:

  1. Timothy Chow10:40 AM, May 05, 2011

    I always thought that "structure of complexity classes" referred to things like Ladner's theorem or the Berman-Hartmanis isomorphism conjecture, i.e., properties of a complexity class beyond its mere existence as an arbitrary set of strings.

    ReplyDelete
  2. Anonymous8:49 PM, May 05, 2011

    To answer one of Bill's questions, there have been at least a half-dozen papers on complexity and learning at CCC in the past decade.

    I 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

    ReplyDelete
  3. Anonymous9:51 PM, May 05, 2011

    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
    (subscription required)

    ReplyDelete
  4. GASARCH10:25 PM, May 05, 2011

    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.

    ReplyDelete
  5. John Sidles6:38 AM, May 08, 2011

    It 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.

    ReplyDelete
  6. Paul Beame10:26 PM, May 09, 2011

    Bill,

    You showed the 2008 list in column-major order. In writing out the revisions of the 2007 list from the PC, I assumed that it would be read in row-major 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.)

    ReplyDelete

Subscribe to: Post Comments (Atom)