FOCS 2012 Student Support

I've been asked by Rafail Ostrovsky and David Shmoys to highlight that student support for travelling to FOCS 2012 is still available, and the deadline is this Friday.

They note that they can fund 24-25 people, so people in the US should apply EVEN IF they don't have a paper.

The NSF has been very generous of late in supporting student travel to conferences, and the best way to encourage them to continue is to show that we use the money they give us :). My students have taken advantage of these opportunities in the past, and it's been a great experience for them.

So if you're a student reading this (and I know there are many of you!) or if you're an advisor who may not have the funding to send your student(s) to FOCS, do take advantage of this chance.

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 ?