## Sunday, September 09, 2012

### Things a TCSer should have done at least once

There are many discussions about what things a TCS grad student should know. I thought it might be useful instead to list out some things a theoretician should have done at some point early in their career.

Rules of the game:
• You lose points if you do it as part of a class. If you decide to round an LP in a class on approximations, that's something you're being taught to do. But if you do it as part of solving a problem, then you've also done the difficult job of recognizing that an LP needs to be rounded. That latter skill demonstrates some mastery.
• The goal is not complete coverage of all of TCS; rather, it's coverage of techniques that will come up fairly often, no matter what kinds of problems you look at.
• This list is necessarily algorithms-biased. I doubt you'll need many of these if you're doing (say) structural complexity.
• A similar caveat applies to classical vs quantum computing. While it seems more and more important even for classical computations that one knows a little quantumness, I don't know enough about quantum algorithm design to add the right elements. Comments ?
With those caveats out of the way, here's my list:
• Show that a problem is NP-hard (for bonus points, from some flavor of SAT via gadgets)
• Show a hardness of approximation result (bonus points for going straight from a PCP)
• Prove a lower bound for a randomized algorithm
• Prove a lower bound via communication complexity or even information theory
• Round an LP (bonus points for not just doing the obvious rounding)
• Show an integrality gap for an LP
• Design a primal-dual algorithm
• Use projective duality to solve a problem (bonus points for using convex duality)
• Apply a Chernoff bound (bonus for using negative dependence, Janson's inequality, and an extra bonus for Talagrand's inequality)
• Design an FPT algorithm (maybe using treewidth, bonus for using bidimensionality or kernelization)
• Design a nontrivial exponential time algorithm (i.e an algorithm that doesn't just enumerate, but does something clever)
• Do an amortized analysis (for extra bonus get a log*n bound)
• use an advanced data structure - something beyond van emde Boas trees (extra bonus for exploiting word-size)
• invoke VC dimension to solve a problem
What else ?

1. Observe that some family of graphs is closed under minors or has an excluded subgraph.

2. Start a blog?

3. Successfully alter the amount of RAM in a computer or, failing that, correctly connect a USB peripheral.

4. Poor students. They are going to die of boredom.

5. - Apply von Neumann's minimax principle to argue something interesting that is not about a primal-dual algorithm.

- Use a hybrid argument (crypto, man, crypto).

- Derandomize something.

- Have a paper rejected from SODA (arguably a more notable distinction than getting something rejected from STOC or FOCS).

- Have your work trashed by someone else in a high-profile conference talk.

6. Go on a date with at least one person from outside of math/CS.

7. How far you so-called theoretical computer science guys have strayed from theoretical computer science!! here are some you didn't mention

* Solve a problem by creating a new Turing-complete model of computation (variations on existing models are allowed, but must be original and clever)

* Prove something new and interesting about the class of partial computable functions using induction based on the Church-Kleene-Rosser definition of computable

* Find a novel new application of The Recursion Theorem

* Prove an original new theorem using transfinite recursion in some way

8. I could easily imagine a TCS faculty working in complexity theory or crypto or algorithmic game theory or computational biology never doing 3/4 of those things.

9. Define an interesting model. Extra point if it is related to a problem someone cares about, or if it can be argued that captures an interesting algorithmic feature.