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 ?
- 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
