October 27-30, 2024

Chicago, IL, USA

FOCS Test of Time Awards

The 2024 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science. This is the sixth annual award.  The target years for the Test of Time Awards in 2024 are for papers presented at the FOCS conferences in 1994, 2004, and 2014. Following new guidance from the FOCS Steering Committee this year, while focusing on the target years, the award committee will consider nominations for exceptional papers in other years. (Please see https://tc.computer.org/tcmf/focs-test-time-award/ for more details, including award winners of previous years.)

List of Awardees:

In the 30 year category:

  1. P.W. Shor: Algorithms for quantum computation: discrete logarithms and factoring
  2. D.R. Simon: On the power of quantum computation
  3. M. Sipser, D.A. Spielman: Expander codes

 In the 20 year Category:

  1. Optimal Inapproximability results for Max-Cut and Other 2-Variables CSPs
    by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell
  2. Worst-case to average-case reductions based on Gaussian measures
    by Daniele Micciancio and Oded Regev

 In the 10 year category:

  1. Popular conjectures imply strong lower bounds for dynamic problems,
    by Amir Abboud and Virginia Vassilevska Williams

Nomination Procedure

Nominations should be sent by July 31, 2024 to [email protected] with a subject line of “FOCS TOT nomination“. Nominations should contain an explanation of the technical achievements and the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.

Selection

The winners will be selected by a committee appointed by the FOCS Steering Committee. For 2024 the award committee consists of Julia Chuzoy (Toyota Technological Institute at Chicago), Costis Daskalakis (MIT), Faith Ellen (University of Toronto), Shafi Goldwasser (UC Berkeley), Leonard Schulman (Caltech), and committee chair Jin-Yi Cai (UW-Madison). Following  FOCS Steering Committee’s guidlines, consideration of papers coauthored by committee members will be deferred to after their service as committee members ends.
 
In selecting the Test of Time Award winners, the Committee will pay particular attention to long-term impact. This impact can come in many forms, including:
    Solving a problem of lasting importance,
    Pioneering a new area of research,
    Introducing novel techniques.
 
The committee expects to select one paper for the award from each of the targeted conference years 1994, 2004 and 2014, but may select either more or fewer papers, as well as papers from non-targeted years. The committee may give awards to papers that are not nominated.