Alistair Sinclair and Shafi Goldwasser win inaugural STOC Test of Time awards
CS Profs. Alistair Sinclair and Shafi Goldwasser have won inaugural Test of Time awards at the 2021 Symposium on Theory of Computing (STOC), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). Sinclair won the 20 Year award for his paper, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” which solved a problem that had been open for decades. Goldwasser won the 30 Year award for “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” which showed how to compute a distributed function even if up to one-third of the participants may be failing, misbehaving, or malicious. The awards were presented at the 2021 STOC conference in June.