UChicago/TTIC Researchers Present Several Papers, Win Test of Time Awards at FOCS 2020

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.

Young Faculty, TTIC Collaborations Fuel FOCS 2020 Papers

Both Chuzhoy’s and Tulsiani’s FOCS 2020 papers involved UChicago CS PhD student coauthors, while one of Potechin’s coauthors was a TTIC PhD student, demonstrating the deep cross-fertilization between TTIC and the Department of Computer Science. In all, five PhD students from UChicago CS, two from TTIC, and 1 from the UChicago Department of Mathematics received coauthor credit on the four Chicago-only papers presented at the conference. One UChicago CS student, Fernando Granha Jeronimo, appeared on two different papers. 

“These achievements give some indication of the excitement that the combined Theory group of UChicago and TTIC generates,” Babai said. “The two institutions combined represent a critical mass we can leverage in recruitment of our PhD students, faculty, and in projecting our image to the world.”

Two papers from UChicago assistant professors Drucker and Potechin also demonstrated the strength of the Theory group; each paper reflected recognition for concepts they had invented, their colleagues said.

Drucker’s contribution, “An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature,” was one of only four single-author papers at this year’s FOCS. His paper addressed decision-making under persistent, unfolding uncertainty, utilizing the problem structure of a game against “nature” — an opponent that makes random moves and doesn’t care about the outcome. The model is relevant to many real-world situations, Drucker said, such as an airplane pilot revising a flight course based on changing weather conditions.

In the paper, Drucker describes a new algorithm to discover nearly-optimal strategies for this game. Using carefully-designed parallel recursive calls, Drucker proved “a strong, ‘exponential’ savings over ‘brute-force’ reasoning about all possible sequences of actions and observations,” he said. These savings were previously developed in AI methods for playing chess and similar games where the opponent is playing to win. 

“Such algorithms don't eliminate the need for search whose size grows exponentially in the length of the game; but they do provably accelerate it, increasing the length of games we can handle, and are important for game-playing AI,” Drucker said. “The current work proves for the first time that an analogous exponential savings is also possible for games against a randomly playing Nature.”

In his FOCS 2020 paper, Potechin teamed up with four PhD students to tackle a classical problem in statistical physics: finding the ground state of the Sherrington-Kirkpatrick Hamiltonian. In “Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes,” the researchers attempted to use the sum of squares hierarchy to certify that the approximate ground state determined by an established algorithm is almost optimal.

“Our paper shows that the sum of squares hierarchy fails to give such a certification,” Potechin said. “Since the sum of squares hierarchy is a very powerful model of computation, this gives strong evidence that this certification problem is hard.”

The collaboration involved several students interested in the sum of squares hierarchy: Mrinalkanti Ghosh of TTIC and Fernando Granha Jeronimo, Chris Jones, and Goutham Rajendran of UChicago CS. The size of the team and the involvement of students showcased Potechin’s “amazing mentorship,” Babai said.

“While five coauthors may not be uncommon in areas of applied computing, in Theory, where it is seldom possible to divide up a problem into distinct subareas, it takes extraordinary leadership to get so many students up to speed and involve them in a way that permits each of them to make meaningful contributions,” Babai said.

For a full list of FOCS 2020 accepted papers, visit the conference website.