The 2024 Gödel Prize

The 2024 Gödel Prize is awarded for the following paper:

Ryan Williams: Non-Uniform ACC Circuit Lower Bounds.

Computational Complexity Conference (CCC) 2011.

Journal of the ACM 61(1):1–32 (2014)

The area of circuit lower bounds experienced a series of early successes culminating in the Razborov-Smolensky circuit lower bound. These have led the community to expect advances in the P vs NP question soon to follow. Alas, progress came to an abrupt halt, leaving even the question of non-deterministic time 2ⁿ vs polynomial-size constant-depth circuits with gates that can count modulo some fixed integer (ACC) widely open. This state of affairs remained unchallenged for over two decades, until Williams’ breakthrough result came along. The awarded paper showed that NTIME(2ⁿ) does not have polynomial-size non-uniform ACC circuits.

Williams’ result overcame several barriers against proving circuit lower bounds: the Baker-Gill-Solovay relativization barrier, the Razborov-Rudich natural proofs barrier, and the Aaronson-Wigderson algebrization barrier. The technique that went into its proof is considered nowadays a cornerstone of modern complexity theory. It consists in proving lower bounds via constructing better-than-trivial algorithms for circuit satisfiability.

The “algorithms to lower bounds” paradigm pioneered in the awarded paper opened the door to a rich two-way connection between algorithmic techniques and lower bound techniques. It was strengthened to show that NTIME(n ^poly(log(n)) ) does not have polynomial-size circuits, and to exhibit functions in NP that cannot be computed by fixed-polynomial-size depth-two neural nets. The technique also inspired work on constructing rigid matrices in FNP and other hard objects like randomness extractors, and lower bounds in Kolmogorov complexity. The road that Williams paved between algorithms and complexity lower bounds had considerable impact also on algorithm design. Following the awarded work, Williams and several others have productively used lower-bound techniques from complexity theory to design improved algorithms for central problems, like a surprisingly faster randomised algorithm for the all-pairs shortest path problem based on techniques from the Razborov-Smolensky circuit lower bound.

Award Committee:

Mikołaj Bojańczyk (University of Warsaw)

Irit Dinur (Weizmann Institute)

Yuval Ishai (Technion)

Anca Muscholl (University of Bordeaux, chair)

Tim Roughgarden (Columbia University)

Luca Trevisan (Bocconi University)