{"id":85,"date":"2025-01-31T19:43:36","date_gmt":"2025-01-31T19:43:36","guid":{"rendered":"https:\/\/focs.computer.org\/2025\/test-of-time-awards\/"},"modified":"2025-12-23T21:52:49","modified_gmt":"2025-12-23T21:52:49","slug":"test-of-time-awards","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2025\/test-of-time-awards\/","title":{"rendered":"Test of Time Awards"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

\nFOCS Test of Time Awards<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

The 2025 FOCS Test of Time Awards<\/a><\/strong>, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science. This is the seventh annual award.\u00a0 The target years for the Test of Time Awards in 2025 are for papers presented at the FOCS conferences in 1995, 2005, and 2015. Following guidance from the FOCS Steering Committee, 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\/<\/a>\u00a0for more details, including award winners of previous years.)<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

List of Awardees<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In the 30 year category:<\/h3>
  • B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan: Private Information Retrieval<\/em><\/li>
  • P. Auer, N. Cesa-Bianchi Y. Freund, R. Schapire: Gambling in a rigged casino: The adversarial multi-armed bandit problem<\/em><\/li><\/ul><\/div>

    \u00a0In the 20 year Category:<\/h3>
    • A. Mehta, A. Saberi, U. Vazirani, V. Vazirani: AdWord and Generalized Online Matching<\/em><\/li>
    • S. A.Khot, N. K. Vishnoi: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type<\/em><\/li>
    • A. T. Kalai, A. R. Klivans, Y. Mansour, R. A. Servedio: Agnostically Learning Half Spaces<\/em><\/li><\/ul><\/div>

      \u00a0In the 10 year category:<\/h3>
      • N. Bitansky, V. Vaikuntanathan: Indistinguishability Obfuscation from Functional Encryption<\/em><\/li>
      • M. G\u00f6\u00f6s, T. Pitassi, T. Watson: Deterministic Communication vs. Partition Number<\/em><\/li>
      • Y. T. Lee, A. Sidford, S. Chiu-Wai Wong: A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization<\/em><\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
        \n\t\t\t\t\t\t
        \n\t\t\t\t\t
        \n\t\t\t
        \n\t\t\t\t\t\t
        \n\t\t\t\t
        \n\t\t\t\t\t

        Award citations<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
        \n\t\t\t\t
        \n\t\t\t\t\t\t\t\t\t
        • Private Information Retrieval
          <\/b>Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
          36th FOCS, 1995<\/li><\/ul>

          This remarkable paper introduced a fundamental primitive in the field of cryptography:\u00a0 how to query a data base fully preserving the privacy of the query. The work introduced the notion of private information retrieval (PIR), gave the first protocols that allow users to retrieve items from distributed databases without revealing which item \u2014 thereby founding a new subfield at the intersection of cryptography, information theory, and complexity theory. Its definitions and constructions have shaped decades of research, enabled practical variants, and remain a cornerstone for privacy-preserving data access.<\/p><\/blockquote>

          \u00a0<\/div>
          • Gambling in a rigged casino: The adversarial multi-armed bandit problem
            <\/b>Peter Auer, Nicol\u00f3 Cesa-Bianchi Yoav Freund, Robert Schapire
            36th FOCS, 1995<\/li><\/ul>

            This paper introduced the adversarial<\/i>\u00a0multi-armed bandit as well as (what later become known as) the contextual bandit problems, deviating from the online decision-making tradition that made stochastic assumptions about the sequence of decisions. The paper provided\u00a0the first algorithms achieving sub-linear regret for these problems and a tight lower bound for the smallest attainable regret, introducing some key algorithmic and lower bounding techniques that continue to inspire contemporary developments. By showing that\u00a0robust performance guarantees are feasible even when payoffs are chosen by an adversary, the paper has had a profound influence in the theory and practice of algorithms in settings ranging from the more benign to the more worst-case, including\u00a0reinforcement learning, online convex optimization, game theory and multi-agent learning. Meanwhile,\u00a0contextual bandits now constitute the algorithmic\u00a0underpinnings of personalization in online content recommendations and display advertising,\u00a0and are increasingly being applied in health care.<\/p><\/blockquote>

            \u00a0<\/div>
            • AdWord and Generalized Online Matching
              <\/b>Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
              46th FOCS,\u00a0 2005<\/li><\/ul>

              This paper introduced a generalization\u00a0of\u00a0the classical online bipartite matching problem, modeling questions\u00a0in\u00a0online advertising. The algorithm, as well as the notion\u00a0of\u00a0a trade-off\u2013revealing LP used\u00a0in\u00a0its design, had a significant impact\u00a0on\u00a0the theory and practice\u00a0of\u00a0electronic commerce.<\/p><\/blockquote>

              \u00a0<\/div>
              • The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type
                <\/b>Subhash A.Khot, Nisheeth K. Vishnoi
                46th FOCS,\u00a0 2005<\/li><\/ul>

                This paper solved an important question both in the theory of hardness of approximation, as well as in the geometric theory of metric embeddings. The paper shows super-constant integrality gaps for unique games, for the basic SDP relaxation program, even when enhanced with triangle inequality constraints. To date, this is still the strongest known program in the SDP or SoS hierarchy for which unique games are provably hard. On top of that, the result has an interesting\u00a0 geometric interpretation, showing that every embedding of “negative type” metrics into ell_1 must have non-constant distortion, thus disproving a conjecture by Goemans and Linial.<\/p><\/blockquote>

                \u00a0<\/div>
                • Agnostically Learning Half Spaces
                  <\/b>Adam T. Kalai, Adam R. Klivans, Yishay Mansour Rocco A. Servedio
                  46th FOCS,\u00a0 2005<\/li><\/ul>

                  This paper provided a breakthrough result in computational learning theory: An efficient learning algorithm for the class of halfspaces (linear separators) that could tolerate adversarial <\/i>label noise, under reasonable distributional assumptions.\u00a0 Prior to this work, there were almost no positive results for learning interesting concept classes with noise, except in the most benign of noise models.\u00a0 Moreover, connections to cryptography suggested that efficiently learning halfspaces with adversarial label noise might be impossible in the distribution-free setting.\u00a0 Kalai, Klivans, Mansour, and Servedio overcame this barrier, showing that under a wide class of distributions (e.g., log-concave distributions), halfspaces \ud835\udc50\ud835\udc4e\ud835\udc5b\u00a0be efficiently learned regardless of adversarial label noise.\u00a0 The work contributed to a fundamental shift in the field’s perspective, leading to an outpouring of new positive results for learning geometric concepts in more challenging noise models and with relaxed distributional assumptions.<\/p><\/blockquote>

                  \u00a0<\/div>
                  • Indistinguishability Obfuscation from Functional Encryption
                    <\/b>Nir Bitansky, Vinod Vaikuntanathan
                    56th FOCS,\u00a0 2015<\/li><\/ul>

                    This paper made an important conceptual contribution by demonstrating how succinct public-key functional encryption is sufficient to construct indistinguishability obfuscation which is widely viewed as the \u201cuniversal cryptographic primitive,\u201d capable of yielding nearly any cryptographic functionality. Its techniques shaped subsequent work enabling simpler constructions and influencing a generation of follow-up research.<\/p><\/blockquote>

                    • Deterministic Communication vs. Partition Number
                      <\/b>Mika G\u00f6\u00f6s, Toniann Pitassi, Thomas Watson
                      56th FOCS,\u00a0 2015<\/li><\/ul>

                      This paper separates the logarithm of the partition number and the deterministic communication complexity of a function, resolving a long-standing open problem and moreover, stimulating a flurry of works on lifting theorems of various kinds. Lifting, first introduced by Raz and Mckenzie, is the idea of first proving a separation in the setting of query complexity and then to “lifting” it to communication complexity.<\/p><\/blockquote>

                      • A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
                        <\/b>Yin Tat Lee, Aaron Sidford,\u00a0 Sam Chiu-Wai Wong
                        56th FOCS,\u00a0 2015<\/li><\/ul>

                        This paper showed how to solve convex programs in the cutting-plane framework, using a (near-)linear number of calls to a separation oracle while performing a (near-)cubic number of arithmetic operations. This result both\u00a0 improved and unified prior methods for solving this classic problem, yielding improved algorithms for submodular minimization, matroid intersection, and other combinatorial optimization problems.<\/p><\/blockquote>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

                        \n\t\t\t\t\t\t
                        \n\t\t\t\t\t
                        \n\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t
                        \n\t\t\t\t\t

                        FOCS 2025 test of time committee<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
                        \n\t\t\t\t
                        \n\t\t\t\t\t\t\t\t\t
                        • Shafi\u00a0 Goldwasser (chair)<\/li>
                        • Julia Chuzhoy<\/li>
                        • Costis Daskalakis<\/li>
                        • Irit Dinur<\/li>
                        • Ryan O\u2019Donnell<\/li>
                        • Piotr Indyk<\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

                          FOCS Test of Time Awards The 2025 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 seventh annual award.\u00a0 The target years for the Test of Time Awards in 2025 are for papers presented at the FOCS conferences […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":"","_members_access_role":[],"_members_access_error":""},"class_list":["post-85","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages\/85","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/comments?post=85"}],"version-history":[{"count":0,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages\/85\/revisions"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/media?parent=85"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}