ACM Special Interest Group on Algorithms and Computation Theory

2023 SIGACT Distinguished Service Award and Gödel Prize

We are pleased to congratulate the winners of the SIGACT Distinguished Service Award and Gödel Prize for 2023.

  • The SIGACT Distinguished Service Award is presented to Jelani Nelson for outstanding contributions to broadening participation in computer science, and to theoretical computer science in particular. The most prominent demonstration is Jelani’s founding and leading of AddisCoder, a summer program geared toward high-school students in developing countries that introduces them to the fundamentals of computational thinking. Jelani also co-founded the David Harold Blackwell Summer Research Institute, which offers summer research internships to undergraduate students across the U.S. with the aim of increasing the number of African American students pursuing graduate school in the mathematical sciences.
  • The Gödel Prize is awarded to Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, and Thomas Rothvoss for two papers that proved exponential lower bounds on the size of extended formulations for the traveling salesman and matching polytopes.

2022 SIGACT Distinguished Service Award, Knuth Prize, and Gödel Prize

We are pleased to congratulate the winners of the SIGACT Distinguished Service Award, Knuth Prize, and Gödel Prize for 2022.

  • The SIGACT Distinguished Service Award is presented to Rajiv Gandhi for outstanding contributions to mentoring and teaching a large number of high-school and undergraduate students from many different, often non-traditional backgrounds—empowering them to achieve substantially in theoretical computer science and to take an appreciation for theoretical computer science into their other computing endeavors.
  • The Knuth Prize is awarded to Noga Alon for significant contributions, spanning three decades, at the interface between discrete mathematics and computer science, creating and fortifying lasting bridges between the two communities. His works include many seminal results that influenced a wide variety of important research directions in computer science.
  • The Gödel Prize is awarded to Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan for two papers that made transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes.

2021 SIGACT Distinguished Service Award, Knuth Prize, and Gödel Prize

We are pleased to congratulate the winners of the SIGACT Distinguished Service Award, Knuth Prize, and Gödel Prize for 2021.

  • The SIGACT Distinguished Service Award is awarded to Paul Beame for over 20 years of dedicated and effective support of the mission of the Theoretical Computer Science community. Paul’s tireless service, in both official and unofficial roles, has been highly instrumental in ensuring the smooth running and continued vitality of the flagship STOC and FOCS conferences and of SIGACT itself.
  • The Knuth Prize is awarded to Moshe Vardi for outstanding contributions that apply mathematical logic to multiple fundamental areas of computer science.
  • The Gödel Prize is awarded to Andrei Bulatov, Martin E. Dyer, David Richerby, Jin-Yi Cai, and Xi Chen for three papers that are the culmination of a large body of work on the classification of counting complexity of Constraint Satisfaction Problems (CSP), proving an all-encompassing Complexity Dichotomy Theorem for counting CSP-type problems that are expressible as a partition function.

SIGACT Institutes New STOC Test of Time Award

Beginning in 2021 and continuing annually thereafter, “Test of Time” awards will be given to papers published in past STOC conferences that have had exceptional long-term impact. The 2021 STOC Test of Time Awards will be for papers presented at the STOC conferences in 2007–2011, 1997–2001, and 1987–1991. For more information on eligibility and nomination procedures, see the call for nominations.

SIGACT Distinguished Service Award changes eligibility rules and extends 2021 nomination deadline

The SIGACT Distinguished Service Award has adopted a new eligibility rule. The award can be given to an individual or a group of individuals, for a single contribution or for a series of contributions over a career. All living individuals are eligible with the exception of the sitting SIGACT Chair, an individual or a group of individuals who nominated a majority of the current selection committee members, or a member of the current selection committee.

For 2021 only, the deadline to nominate an individual or group for the SIGACT Distinguished Award has been extended by one week, to March 8, 11:59 EST. In future years, the award will return to its regular deadline of March 1, 11:59 EST.

SIGACT Research Highlights Committee

The goal of the SIGACT Research Highlights Committee is to help promote top computer science theory research via identifying results that are of high quality and broad appeal to the general computer science audience. These results would then be recommended for consideration for the CACM Research Highlights section as well as other general-audience computer science research outlets.

Nomination and Selection Process

The committee solicits two types of nominations:

  1. Conference nominations. Each year, the committee will ask the PC chairs of theoretical computer science conferences to send a selection of up to three top papers from these conferences (selected based on both their technical merit and breadth of interest to non-theory audience) and forwarding them to the committee for considerations.

  2. Community nominations. The committee will accept nominations from the members of the community, including self-nominations. Each such nomination should summarize the contribution of the nominated paper and also argue why this paper is suitable for broader outreach. The nomination should be no more than a page in length and can be submitted at any time by emailing it to Self-nominations are discouraged.

Please submit by October 22, 2021 (Fri).

The Committee

The SIGACT Research Highlights Committee currently comprises the following members:

2020 SIGACT Distinguished Service Award, Knuth Prize, and Gödel Prize

We are pleased to congratulate the winners of the SIGACT Distinguished Service Award, Knuth Prize, and Gödel Prize for 2020.

  • The SIGACT Distinguished Service Award is awarded to Dieter van Melkebeek for his leadership in creating the Computational Complexity Foundation (CCF) and transitioning the annual Computational Complexity Conference to be run under the auspices of the CCF.
  • The Knuth Prize is awarded to Cynthia Dwork for her sustained record of contributions to theoretical computer science over the past four decades.
  • The Gödel Prize is awarded to Robin A. Moser and Gábor Tardos for their algorithmic version of the Lovász Local Lemma in the paper “A Constructive Proof of The General Lovász Local Lemma,” Journal of the ACM 57(2): 11:1-11:15 (2010).

STOC 2020 and TheoryFest to be held online only

Due to the current situation with COVID-19, it was decided that Theory Fest and STOC 2020 will be held online only.

While the organizing committee is still finalizing the format of the conference, authors are being asked to prepare and upload a video recording of a 20-minute presentation of their paper before the conference, so participants can review the videos in advance. Plans are being made to allow for online discussions to happen during the conference itself (third week of June).

More details will be posted here:

SIGACT Membership Drive

As our research community continues to grow and thrive, SIGACT membership has not grown apace. We respectfully urge you to join SIGACT! Membership is very cheap (and does not require ACM membership) – only $15 a year – and by joining you will be lending your support to the many activities that SIGACT undertakes on behalf of the theoretical computer science research community. These include:

  • sponsoring STOC and other theory conferences such as SPAA and PODC, as well as co-sponsoring SODA;

  • awards such as the Knuth, Gödel, and Kanellakis Prizes, the SIGACT Distinguished Service Award, and the best student paper awards at STOC and SODA;

  • supporting the Women in Theory workshop;

  • representing the theoretical computer science community to the ACM and beyond.

In addition to these community benefits, membership comes with individual benefits including voting rights in SIGACT elections, reduced rate for membership in EATCS, reduced conference registration rates at SIGACT-sponsored conferences, access to SIGACT News and announcements sent on the SIGACT email list.

SIG membership does not automatically renew when you renew your ACM membership, and we suspect this may be one reason for the decline in SIGACT membership. So the next time you renew your ACM membership, remember to also join SIGACT or renew your SIG membership! Better yet, why wait? If you’re not a SIGACT member, join right now.

Please do your part to nurture this important resource for our community.


The SIGACT Executive Committee
Tal Rabin, Chair
Ken Clarkson
Valerie King
Shachar Lovett
Chris Umans

SIGACT Distinguished Service Award Prize Increase

The prize for the ACM SIGACT Distinguished Service Award was increased from $1,000 to $3,000. A call for nominations will be announced shortly.

Report on combating harassment and discrimination

The following message is from Sandi Irani, the chair of the ad hoc committee to combat harassment and discrimination in the Theory of Computing community.

A copy of the final report of the committee to address harassment in our community is now posted on the committee web page.

As always, feedback is welcome.