The following Test of Time Awards were awarded at STOC 2023.

The 30-year Test-of Time award recognizes two seminal papers published in 1989 and 1993:

• "When trees collide: An approximation algorithm for the generalized Steiner problem on networks" by Ajit Agrawal, Philip Klein, and R. Ravi (1989); and
• "Quantum complexity theory", by Ethan Bernstein and Umesh Vazirani (1993).

The Agrawal, Klein and Ravi paper introduced a fundamental technique for producing integral solutions with good approximation from linear programming relaxations for a variety of problems. They did so for the generalized Steiner problem, but the primal-dual methodology found use in very broad range of network design algorithms propagated through work of Goemans and Williamson.

The Bernstein, Vazirani paper connected the frame of computation and that of quantum mechanics to begin rich, deep, and continuing work in theoretical computer science, theoretical physics, as well as framing experiments with quantum mechanics as embodied in quantum computing.

The 20-year Test-of-Time award recognizes two seminal papers that were published in STOC 2001 and 2003:

• "A sieve algorithm for the shortest lattice vector problem" by Miklos Atjai, Ravi Kumar, D. Sivakumar (2001); and
• "New lattice-based cryptographic constructions" by Oded Regev (2003).

These papers are both important in the post-quantum cryptography and happen to have outsized impact.

The Ajtai-Kumar-Sivakumar (AKS) paper ushered in a new chapter in the area of lattice algorithms, adding the powerful new technique of sieving to the already formidable toolkit in the field. The AKS algorithm solved the exact shortest vector problem (SVP) on n-dimensional lattices, and presented dramatic improvement over the celebrated Lenstra-Lenstra-Lovasc (LLL) algorithm which solved SVP. It has continued to have impact and appears to be the best possible theoretically and is perhaps suprisingly having some practical impact.

Regev's STOC 2003 paper introduced the highly influential machinery of Fourier analysis on lattices to complexity theory (in the form of worst-case to average-case reductions) and cryptography (in the form of a better public-key encryption, and downstream, many advanced cryptographic functionalities). His paper has had a tremendous impact on the complexity theory of lattices, lattice algorithms and cryptography.

The 10-year Test-of-Time award recognizes a seminal paper published in STOC 2013:

• "Low rank approximation and regression in input sparsity time" by Kenneth L. Clarkson and David P. Woodruff (2013).

In their breakthrough STOC'13 paper, Clarkson and Woodruff for the first time give algorithms whose running time was essentially proportional to the number of non-zero elements in the input matrix. Since its development ten years ago, the Clarkson-Woodruff algorithm has had a huge influence on both theory and practice of numerical linear algebra evidenced by the teaching of it in numerous courses as well as its incorporation into a variety of widely used software packages.

Award Committee:

Joan Feigenbaum (Yale)
Michel Goemans (MIT)
Satish Rao (Berkeley, chair)
Mike Paterson (Warwick)