Some Problems Have No Solutions: 30 Years Later, Papers on the Topic Earn Test of Time Award

The Institute of Electrical and Electronics Engineers Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) has recognized the long-term impact of two papers co-written by Illinois Institute of Technology College of Computing Dean Lance Fortnow 30 years ago.

Fortnow was honored with the Test of Time Award by the TCMF at its 61st annual Symposium on Foundations of Computer Science for “Algebraic Methods for Interactive Proof Systems” and “Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols.”

Fortnow was a young assistant professor in the computer science department at the University of Chicago when he co-wrote “Algebraic Methods for Interactive Proof Systems” with Carsten Lund, Howard Karloff, and Noam Nisan in 1990. Lund was Fortnow’s Ph.D. student at the time, and now works at AT&T Labs Research. Karloff was a fellow professor, who now works at Goldman Sachs. Nisan, then and now a professor at the Hebrew University of Jerusalem, went to graduate school with Fortnow.

“The paper gives an ‘interactive proof’ to show that solutions for some problems don’t exist,” Fortnow says. “For example, given a map, a powerful being Hera can convince a mortal Harry that there is no method to color the map with three colors unless two bordering countries get the same color. In this model, Harry can ask the powerful being randomly generated questions to determine a solution does not exist.”

Fortnow and Lund teamed up with László Babai, a fellow University of Chicago professor, to write “Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols.”

“It examines a different model and shows that there is a very long proof written in a huge book, far bigger than Harry can fully read,” Fortnow says. “But, by checking a small number of randomly chosen places, Harry can be convinced that the proof is correct.”

The Babai-Fortnow-Lund work has some surprising applications to show that we cannot find solutions, even close to optimal, to many optimization problems. 

These are the second annual FOCS Test of Time Awards. The 2020 award winners were presented at the FOCS symposium, held virtually, on November 16–19. The awards recognize the long-term impact of research in forms that include opening up a new area of research, introducing new techniques, or solving a problem of lasting importance.

Photo: College of Computing Dean Lance Fortnow