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.


Disqus for The Geomblog