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 ? 

Disqus for The Geomblog