Best Paper Awards
Best Paper Award Recipients
Best Papers (awarded jointly to two papers)
A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory
Martin Grohe, Ken-Ichi Kawarabayashi and Bruce Reed
Dynamic Graph Connectivity in Polylogarithmic Worst Case Time
Bruce Kapron, Valerie King and Ben Mountjoy
Best Student Papers (awarded jointly to two papers)
New Additive Spanners
Simple, Fast and Deterministic Gossip and Rumor Spreading
Best Student Paper Award
A prize of $500 will be awarded to the author(s) of the best student-authored paper (or split between more than one paper if there is a tie). A paper is eligible if all of its authors are full-time students at the time of submission. This must be indicated in the submission process.
Best Paper Award
The program committee may designate up to three papers accepted to the conference as SODA Best Papers. Every submission is automatically eligible for this award.
The following rules for Best Paper Awards at theory conferences were developed by a committee consisting of Paul Beame, David Johnson, Prabhakar Raghavan, Eva Tardos and David Williamson (Chair).
The Program Committee may designate up to three papers accepted to the conference as SODA Best Papers.
Each author on each of the selected papers will receive a certificate or plaque with the name of the award, the name of the paper, and the names of the authors of the paper, to be awarded at the Business Meeting that year.
The main criterion for selection is the same as for being a top-rated paper in the conference: introduction of a strong new technique, solution of a long-standing open problem, introduction and solution of an interesting and important new problem, etc. These are the characteristics associated with giving a paper the highest score.
Additionally, the committee should have substantial confidence in the correctness of the paper. While the committee may choose to accept papers to appear in the conference while lacking confidence that the paper is correct, such papers should not be recipients of the Best Paper Award. Since only abstracts are submitted to the conference, the committee may, after accepting a paper to the conference, inform the authors that the paper is being considered for the Award, and request additional details. It is suggested that the committee finalize its decisions on the Award in time to have the recipients listed in the proceedings of the conference. However, the committee may choose to use the time up until the conference itself to continue reviewing the papers.
The committee should verify that the final proceedings version of the paper meets the high promise of the submitted abstract.
If no paper meets the criteria above, then no award need be given.
If a paper qualifies for the Best Student Paper Award, it should not be disqualified from being considered for the Best Paper Award, and vice versa; a paper meriting both Awards should be given both Awards.