Test of Time Awards Highlight Enduring Innovation

CS professors have been honored with Test of Time Awards in 2025, distinctions granted annually by premier computer science conferences to research that has demonstrated enduring impact—work that continues to shape the discipline long after its initial publication.

At the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), Rocco Servedio, Adam T. Kalai, Adam R. Klivans, Yishay Mansour were honored for their 2005 paper, Agnostically Learning Half Spaces. The research delivered a breakthrough in computational learning theory by proving that halfspaces can be efficiently learned under adversarial label noise, overturning prior assumptions of impossibility. Its results reshaped the field, sparking a wave of new advances in learning geometric concepts under more complex noise models and broader distributional settings.

Also at FOCS 2025, Toniann Pitassi, Mika Göös, and Thomas Watson received recognition for their 2015 paper, Deterministic Communication vs. Partition Number. The paper established a separation between the logarithm of the partition number and the deterministic communication complexity of a function, resolving a long‑standing open question and sparking extensive research on lifting theorems. The lifting framework, introduced by Raz and McKenzie, involves proving separations in query complexity and then extending them to communication complexity.