Friday, February 01, 2008

The Final Two

Run a tournament that does a series of comparisons to decide a winner. No matter what algorithm you use, there will always be that final comparison, before which we had exactly two possible candidates to emerge victorious.

In America we are seeing those final rounds play out in a variety of forums this week. The Republican and Democratic fields have been whittled down heading into Super Tuesday where nearly half the states, including Illinois, have their primaries. The Super Bowl on Sunday evening pits the final two football teams against each other.

So what will it be? Clinton or Obama? McCain or Romney? Patriots or Giants? Stay tuned.


  1. Does anyone know when the papers accepted to STOC'08 will be announced? Apparently, they asked Ack from the accepted papers to re-collect the data and announce the list. It does not seem right to me since lots of authors just read the acceptance/rejection sentence and forget about the rest. Anyway, the already have such a list and this list is not the final schedule. I think announcing the list of accepted papers should be done almost the same time that the notifications are sent. Don't you think so?

  2. And the reviews for STOC 2008 have not been sent yet -- although the acceptances/rejections have been announced a week ago. What's with that?

  3. it will be hillary and mccain.

  4. It will be Gravel and Paul, together!

  5. Obama, McCain and Patriots.

  6. Google or Microsoft?

  7. I think announcing the list of accepted papers should be done almost the same time that the notifications are sent. Don't you think so?

    It is nice to wait at least a day or so, so that authors learn first hand of the decision through an email. After that, the earlier the better.

  8. I got my reviews for STOC at around 1:30pm today (Friday).

  9. Occasionally there are paper merges that require some discussion with the authors prior to announcement of the list so a few days difference between e-mails and the full list is not unusual.

  10. While it is true this year, there is an assumption of a binary comparison that is both not always true in the US (1992) and is very far from true in many other democracies.

  11. For those not sleeping (or on a different time zone), the list of accepted papers for STOC'08 is at


  12. Any breakdown on which researcher/school has the most publications?

    I noticed 3 each from at least:
    Madhu Sudan
    Avrim Blum
    Adam Kalai

  13. No claim of correctness, some authors have misspelled or inconsistent names.

    3 Madhu Sudan
    3 Avrim Blum
    3 Adam Tauman Kalai
    2 Yuval Ishai
    2 Tali Kaufman
    2 Shafi Goldwasser
    2 Shachar Lovett
    2 Santosh Vempala
    2 Ryan O'Donnell
    2 Rohit Khandekar
    2 Prasad Raghavendra
    2 Parikshit Gopalan
    2 Nisheeth K. Vishnoi
    2 Nikhil Bansal
    2 Moni Naor
    2 Katrina Ligett
    2 Joseph (Seffi) Naor
    2 Guy Rothblum
    2 Daniel Spielman
    2 Chris Peikert
    2 Avi Wigderson
    2 Amir Shpilka
    2 Adam R. Klivans
    2 Aaron Roth

  14. And if you divide by number of authors on a paper:
    1.33333333333333 Shachar Lovett
    1.25 Prasad Raghavendra
    1.25 Madhu Sudan

  15. And if you divide by number of authors on a paper:

    Since the unnormalized list produces a much better selection of names, this suggests that dividing by number of authors is a very flawed metric.

  16. It will be Hillary vs. McCain, and then McCain!

  17. No clue on the democratic side. For the Republicans it will go down to the wire with Ron Paul's vote growing steadily. If Paul wins the party he wins the presidency. If Mitt/McCain win they go down in flames.

  18. Ron Paul?!
    No chance! He hasn't been a serious candidate up until now, according to all polls.

  19. you theorists are lame - lance starts a useful and interesting discussion about politics and super bowl, and all you do is talk about stoc 2008 acceptances?

    lame, really lame