The IEEE Symposium on Foundations of Computer Science, known colloquially as FOCS, is one of the premier conferences for theoretical computer science research. This year, the University of Chicago left its mark on the highly competitive FOCS meeting, presenting several research papers and receiving Test of Time awards for past work by current and former faculty.
In total, eight papers at this year’s FOCS were authored or coauthored by faculty and students from UChicago CS and the Toyota Technological Institute at Chicago (TTIC), an academic computer science institute located in Hyde Park closely affiliated with UChicago CS. The papers, including four with only UChicago and TTIC authors and two led by junior faculty Andrew Drucker and Aaron Potechin, tackle decision-making under uncertainty, classical problems in statistical physics, and other critical topics in computation theory.
The department was also heavily represented in the conference’s Test of Time Awards, which honored three 1990 papers, two of which were written at the University of Chicago, for their “substantial, lasting, broad, and currently relevant impact.” One paper, "Algebraic Methods for Interactive Proof Systems,” was coauthored by then-faculty Lance Fortnow (now Dean of the College of Computing at Illinois Institute of Technology) and Howard Karloff (now a VP of Goldmann-Sachs, after a long and successful career in academia) and PhD student Carsten Lund (currently at AT&T Labs). Fortnow and Lund also coauthored another award winning paper, "Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols,” with László Babai, Bruce V. and Diana M. Rauner Distinguished Service Professor in the Departments of Computer Science and Mathematics.
The three 1990 Test of Time award papers explored the power of interactive proofs, a concept co-invented by Babai in 1985 for which he shared the Gödel Prize in 1993. The first paper “produced a breakthrough that fundamentally changed our understanding of the power of interactive proofs, showing that efficient interactive proofs exist for all languages in the polynomial-time hierarchy,” the award committee wrote.
Babai’s paper with Fortnow and Lund (the “BFL paper,” for short) triggered a revolution in the theory of approximation algorithms, a thriving area of theoretical research today. It continues to influence the field, recently providing inspiration for a breakthrough in quantum complexity theory.
“The award citation explicitly attributes the first realization of the hugely successful concept of
‘probabilistically checkable proofs’ (PCPs) to the BFL paper, even though this terminology was only introduced two years later, a fact that has so far largely obscured the BFL paper's accomplishment,” said UChicago CS Professor Janos Simon. “For the past 28 years, PCPs have been at the core of the theory of approximation algorithms” — an area studied today by Lorenzo Orecchia of UChicago CS and Julia Chuzhoy, Madhur Tulsiani, and Yury Makarychev of TTIC.