A. I. Barvinok, “A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension Is Fixed”
This exceptional paper presented the first polynomial time algorithm for counting the number of lattice points inside a polyhedron (equivalently, the number of feasible solutions to an integer program) in any fixed dimension d. Previously a polynomial time algorithm was known only for d ≤ 4. The paper makes ingenious use of Brion’s identity for exponential sums over polyhedra, as well as other tools such as Laurent expansion and decompositions into primitive cones.
The paper gives a complete solution to a natural problem. Its method is elegant and innovative. The types of analytical tools used in the paper have seen further significant development in recent years. The algorithm in the paper has had wide ranging applications in many areas from mathematical programming to algebraic geometry. The result itself has been improved in some aspects but has never been superseded.
R. Kleinberg and T. Leighton, “The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions”
This outstanding paper initiated the field of learning from experience with posted prices. It considers a seller who has an unlimited supply of some item (such as a song) and wants to maximize their profit when interacting with a pool of buyers, each of whom wants at most one copy. The benchmark is regret minimization, the difference in expected revenue between a seller who fixes a single price in advance, based on knowledge about how much the buyers will pay, and a seller who sets the price for each buyer using an online strategy. The paper derives upper and lower bounds, which match to within a small factor, in three different settings: when all buyers have the same valuation, when buyers’ valuations are independently chosen from the same probability distribution, and when buyers are adversarial, but oblivious to the random choices made by the seller.
The paper makes a clear connection between posted pricing and the multi-armed bandit problem and started several lines of work in bandit learning, including bandit learning for dynamic pricing with limited supply, bandit learning for contextual dynamic pricing, and bandits with continuous actions. It was the first paper to consider regret minimization in the context of mechanism design, showing the power of this technique in a new and important context.
S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters, “Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits”
This remarkable paper gave the first candidate solution to the problem of general-purpose software obfuscation. The ideal obfuscator would convert any computer program into an equivalent program that gives no information about the original program apart from its functionality. While such an obfuscator would have extremely powerful applications, earlier work showed that it is impossible to achieve, and introduced instead a weaker notion called indistinguishability obfuscation (IO): the obfuscated versions of any two equivalent programs are indistinguishable. It remained unclear both whether IO is achievable, and whether it would be useful.
Amazingly, this paper showed both. It was the first to give a candidate solution with heuristic evidence that it satisfies IO. Moreover, it was the first to give a significant application of IO: it showed that IO can solve the central open problem in functional encryption. Since publication, a long sequence of follow-up works have shown that IO can be used to achieve a variety of objectives in cryptography for which no other approach was known.
The 2023 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 fifth annual award. The target years for the Test of Time Awards in 2023 are for papers presented at the FOCS conferences in 1993, 2003, and 2013, which are each considered for separate awards.
Nominations should be sent by July 31, 2023 to [email protected] with a subject line of “TOT nomination”. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.
The winners will be selected by a committee appointed by the FOCS Steering Committee. For 2023 the award committee consists of Jin-Yi Cai (University of Wisconsin), Faith Ellen (University of Toronto), Leonard Schulman (Caltech), Alistair Sinclair (UC Berkeley), Éva Tardos (Cornell University), and committee chair David Zuckerman (UT Austin).
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:
The committee expects to select exactly one paper for the award associated with each of the targeted years 1993, 2003 and 2013 conferences, but may select up to three papers in each category. The committee may give awards to papers that are not nominated.
While papers in the target years will be favored, the committee may award in each category nominated papers published up to four conferences earlier, if it concludes that the nominated papers were not awarded by prior committees despite their obvious worthiness due to constraints or neglect. Thus, in exceptional circumstances, papers published at FOCS 89-92 can compete for the award targeting the 1993 conference, and similarly for the other two awards.