A few weeks ago, Suresh wrote a post
Things a TCSer should have done at least once with the caveat
This list is necessarily algorithms-biased. I doubt you'll need many of these if you're doing (say) structural complexity.
Basically begging a response. So here is what every structural complexity theorists should have done.
- Define a new complexity class that has some reason for being.
- To keep balance in the world, you should also collapse two other complexity classes.
- While you are at it, separate two complexity classes that weren't separable before.
- Create a new relativized world. Extra points if in this work you collapse two complexity classes while separating two others.
- Use Kolmogorov complexity, information theory or the probabilistic method as a proof technique. They are really all the same technique in disguise.
- Use the sunflower lemma, or the Local Lovasz lemma, or some other weird probabilistic or combinatorial lemma just for the fun of it.
- Invoke VC dimension to solve a problem. I should have at least one in common with Suresh and Sauer's lemma is sometimes useful in complexity.
- Have a theorem that starts "Assuming the extended Riemann hypothesis..."
- Give a "simpler" proof of a nasty theorem.
- [Advice given by Noam Nisan many moons ago] Try to settle P v NP. In both ways. Only by really trying and failing can you understand why the easy stuff doesn't work.
"Define a new complexity class that has some reason for being."
ReplyDeleteDefine 'some reason' please. One reason would be to cross it off the Complexity Theorist bucket list. That's some reason.
You have the qualifier "structural" in your post but not your title so your list sounds not quite as general wrt complexity as Suresh's is wrt algorithms. Question for readers: What would you add to the list if you got rid of the qualifier?
ReplyDeleteWhat exactly is "structural complexity" and how is it different from computational complexity? I think it's time to retire the term.
ReplyDelete@Rahul: See http://en.wikipedia.org/wiki/Structural_complexity_theory. The key sentence is: "In structural complexity the main focus is on complexity classes, as opposed to the study of how individual problems behave, or the analysis of individual algorithms." So structural complexity studies things like the relationship between complexity classes. This is in contrast to concrete complexity, which studies things like unconditional lower bounds for specific problems in various models of computation.
ReplyDelete" ... concrete complexity, which studies things like unconditional lower bounds for specific problems in various models of computation."
DeleteA model of computation naturally defines a complexity class. Getting an unconditional lower/upper bound then amounts to putting a problem out of/into a complexity class.
I completely agree with Rahul.
In the fourth rule of the game, Suresh states another caveat: his list doesn't include anything related to quantum algorithms, mostly because he "doesn't know enough about quantum algorithm design to add the right elements". I can't see any comment to his post that responds to this. @Scott (Shtetl-Optimized): can I expect you to be as prompt as Lance? :)
ReplyDeleteDefine a new complexity class that has some reason for being.
ReplyDeleteUnder my definition of "reason for being" there are barely a dozen of those.
Rahul: I agree that structural complexity is an outdated name but it is also clear that Lance's bucket list misses out on aspects of complexity that is unrelated to complexity classes.
ReplyDelete* Prove an unconditional lower bound on the complexity of an important computational problem.
Such a result might not produce a single new separation between complexity classes but might simply allow one to better understand the problem at hand.
Attempting to settle P versus NP isn't sufficient; one should speculate on a world in which both P==NP AND P!=NP are true simultaneously.
ReplyDelete"Things a Complexity Theorist Should Do At Least Once..."
ReplyDeleteWin a MacArthur award?
Congrats Maria Chudnovsky and Dan Spielman.
Actually this is a question I thought about (not as a complexity theorist or TCSer but as a mathematician interested in these areas). I had (decades ago) a list of my own which is quite separate from both Suresh and Lance (but perhaps too banale). I dont remember all of it but here is what I remember.
ReplyDelete1) Say something interesting about sorting and or searching
2) Say something interesting about matching
3) Say something interesting about linear programming
4) Say something intersting about trees/greedy algorithms/matroids
5) Say something interesting about integer programming
6) Say something intersting about discrete Fourier transform
7) Say something interesting about primality and/or factoring.
I has a few more items on the list which I do not remember right now.