STOC 2023

STOC 2023 is the 55th Annual ACM Symposium on Theory of Computing. It will be held on June 20-23, 2023 in Orlando, Florida.

Perhaps the best paper ever at STOC was by Stephen Cook. His 1971 STOC paper The Complexity of Theorem Proving Procedures formalized the notions of polynomial-time and started the search to prove is not equal to .

See this for more.

Papers with Pointers

Many web sites on STOC 2023 list the accepted papers but not with pointers. We planned to create these links ourself but we discovered this site that already has them:

List of papers with pointers.

This saved us having to create the pointers. Try them—fun to see the accepted papers.

The Program Committee

Thanks to the program committee for working so hard on putting together such a terrific program.

• Amir Abboud (Weizmann Institute of Science)

• Josh Alman (Columbia University)

• Andris Ambainis (University of Latvia)

• Nima Anari (Stanford University)

• Srinivasan Arunachalam (IBM Thomas J. Watson Research Center)

• Petra Berenbrink (Universitat Hamburg)

• Aaron Bernstein (Rutgers University)

• Aditya Bhaskara (University of Utah)

• Sayan Bhattacharya (University of Warwick)

• Eric Blais (University of Waterloo)

• Hans Bodlaender (Utrecht University)

• Adam Bouland (Stanford University)

• Anne Broadbent (University of Ottawa)

• Mark Bun (Boston University)

• Keren Censor-Hillel (Technion)

• Timothy Chan (University of Illinois at Urbana-Champaign)

• Arkadev Chattopadhyay (Tata Institute of Fundamental Research)

• Chandra Chekuri (University of Illinois at Urbana-Champaign)

• Xue Chen (University of Science and Technology of China)

• Gil Cohen (Tel Aviv University)

• Dana Dachman-Soled (University of Maryland College Park)

• Anindya De (University of Pennsylvania)

• Shahar Dobzhinski (Weizmann Institute of Science)

• Shaddin Dughmi (University of Southern California)

• Vida Dujmovic (University of Ottawa)

• Yuval Filmus (Technion)

• Sumegha Garg (Stanford University)

• Rong Ge (Duke University)

• Elena Grigorescu (Purdue University)

• Shuichi Hirahara (National Institute of Informatics, Japan)

• Zhiyi Huang (University of Hong Kong)

• Sungjin Im (University of California, Merced)

• Giuseppe Italiano (LUISS University)

• Ken-ichi Kawarabayashi (National Institute of Informatics, Japan)

• Sanjeev Khanna (University of Pennsylvania)

• Robin Kothari (Google Research)

• Marvin Kunnemann (TU Kaiserslautern)

• Rasmus Kyng (ETH Zurich)

• Sophie Laplante (Universite Paris Cite)

• Hung Le (University of Massachusetts, Amherst)

• Daniel Lokshtanov (University of California, Santa Barbara)

• Sepideh Mahabadi (Microsoft Research)

• Nicole Megow (Universitat Bremen)

• Slobodan Mitrovic (University of California, Davis)

• Ankur Moitra (Massachusetts Institute of Technology)

• Shay Moran (Technion and Google Research)

• Christopher Musco (New York University)

• Krzysztof Onak (Boston University)

• Rotem Oshman (Tel Aviv University)

• Prasad Raghavendra (University of California, Berkeley)

• Susanna Rezende (Lund University)

• Robert Robere (McGill University)

• Alon Rosen (Bocconi University and Reichman University)

• Ron Rothblum (Technion)

• Alex Russell (University of Connecticut)

• Laura Sanita (Bocconi University)

• Thatchaphol Saranurak (University of Michigan)

• Tselil Schramm (Stanford University)

• Rocco Servedio (Columbia University), Chair

• Tasos Sidiropoulos (University of Illinois at Chicago)

• Alex Slivkins (Microsoft Research)

• Srikanth Srinivasan (Aarhus University)

• David Steurer (ETH Zurich)

• Ola Svensson (EPFL)

• Chaitanya Swamy (University of Waterloo)

• Madhur Tulsiani (Toyota Technological Institute at Chicago)

• Christos Tzamos (University of Wisconsin-Madison)

• Muthu Venkitasubramaniam (Georgetown University)

• Ben Lee Volk (Reichman University)

• Andreas Wiese (Technical University of Munich)

• Mary Wootters (Stanford University)

• Yuichi Yoshida (National Institute of Informatics, Japan)

• Huacheng Yu (Princeton University)

Open Problems

I hope having the list of accepted papers with links is of some value. Cook’s paper might be the best ever, but it did not get the award for best paper at the time. Here are some of the more recent best papers:

2020 Improved Bounds for The Sunflower Lemma
2019 The Reachability Problem for Petri Nets is Not Elementary

I like the second one above for personal reasons that I expounded long ago here, and which Ken expanded on here.