Professor Babai scoops up three ACM SIGACT awards

Last summer László Babai received the STOC Best Paper award, the ACM SIGACT Distinguished Service Prize, and the Edsger Dijkstra Prize in Distributed Computing.

Professor Babai received the Symposium on Theory of Computing (STOC) 2016 Best Paper Award for his paper “Graph Isomorphism in quasipolynomial time.”   

This is the result Babai first announced in the UChicago CS/Math “Combinatorics and Theoretical Computer Science” seminar in November 2015 that drew an overflow audience of over 200 to our largest auditorium, Kent 120.  The result was reported in a number of blogs and science magazines.  The full paper is posted on arXiv (article 1512.03547).  Ever since the announcement, Babai has been touring the country and the world, giving lecture series and marathon seminars about this work.

Professor Babai also received the 2016 ACM SIGACT Distinguished Service Prize.

The prize is given annually to an individual who has made substantial service contributions to the Theoretical Computer Science community.

Professor Babai was recognized specifically “for helping to make the latest theoretical computer science results accessible to all researchers.”  While Babai's efforts in this direction predate the internet age, more recently he “has been a leading advocate for open  access in the theoretical computer science community.”  He was recognized in particular for founding the free online journal, “Theory of Computing,” in 2005. “Babai continues to serve as its founding editor-in-chief. Theory of Computing has become one of the strong, mainstream academic journals in theoretical computer science remaining at no cost to authors, readers or libraries. To create and maintain this journal, Babai inspired a number of computer scientists, […] to serve as editors and manage the web presence and authoring/reviewing tools. Theory of Computing is a shining example of how a visionary leader and a dedicated group of volunteers can create and maintain a high-quality fully open access journal.”

Lastly, Professor Babai received the 2016 Edsger W. Dijkstra Prize in Distributed Computing.

A test of time award, “the Dijkstra Prize is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing have been evident for at least a decade.”

The paper being recognized was co-authored by Noga Alon, Alon Itai, and Professor Babai in 1984 when Babai first came to Chicago as a visitor.

The “fascinatingly simple” algorithm described in the paper “has played a significant role in popularizing Distributed Computing to the broader Computer Science community. It is one of the most well-known distributed algorithms, and perhaps the one covered most frequently in general algorithms courses and textbooks, especially those on randomized algorithms,”  according to the citation.

The award was presented at the Principles of Distributed Computing (PODC'16) conference and is jointly awarded by PODC and its European sister conference, the International Symposium on Distributed Computing (DISC).

As Babai likes to point out, the award also represents a tribute to the energy and dedication of Bob Soare, founding chair (1983) of the UChicago CS Department, who jumpstarted the department with a vigorous visitor program.  Alon was a short-term visitor, while Itai and Babai were among the first long-term visitors in Soare's program at the time this paper was written.

These awards come on the heels of Babai's 2015 recognitions: his election as a Fellow of the American Academy of Arts and Sciences and his Knuth Prize for “multiple visionary contributions  that have transformed the landscape of the theory of computing,” including “pioneer[ing] a new understanding of the notion of mathematical proof.”

Related News

More UChicago CS stories from this research area.
Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
UChicago CS News

Asst. Prof. Rana Hanocka Receives NSF Grant to Develop New AI-Driven 3D Modeling Tools

Feb 28, 2023
Two students looking at a wearable device
UChicago CS News

High School Students Find Their Place in Computing Through Wearables Workshop

Jan 13, 2023
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

UChicago AI Summit Examines Promise and Concerns for Science and Society

Nov 01, 2022
UChicago CS News

Five UChicago CS Students Named to Siebel Scholars 2023 Class

Sep 22, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

High School Students in College Prep Program Visit UChicago CS

Aug 23, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube