STOC 2022

The times listed in this table are in Coordinated Universal Time.

STOC 2022 Program

Monday, June 20

Auditorium

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

Zoom: https://acm-org.zoom.us/j/7960895344

6:45

TCS Women Spotlight Workshop

7:00

Workshop #1: Methods, Challenges, and Applications of Constrained Graph Layouts – Planarity Always Strikes Back

Organizers: Patrizio Angelini (John Cabot University), Giordano Da Lozzo (Roma Tre University)

Workshop #2: Optimizing the Effort of Others: from algorithmic contracts to strategic classification

Organizers: Michal Feldman (Tel Aviv University & Microsoft Research), Brendan Lucier (Microsoft Research)

8:30

Coffee break

9:00

Workshop (cont.)

10:15

Lunch

Student Lunch

Room San Bernardino da Siena and Jacopone da Todi

Session #1: Monday, June 20, 12:00 UTC

Auditorium

1A: Quantum

Chair: Ronald de Wolf

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

1B: Randomness

Chair: Sam Hopkins

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

1C: Graph Algos

Chair: Kasper Green Larsen

Zoom: https://acm-org.zoom.us/j/2547463682

12:00

Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy (video)

Hamoon Mousavi (Columbia University), Seyed Sajjad Nezhadi (University of Maryland) and Henry Yuen (Columbia University)

The Power of Two Choices in Graphical Allocation (video)

Nikhil Bansal (University of Michigan) and Ohad N. Feldheim (Hebrew University in Jerusalem)

The Shortest Even Cycle Problem is Tractable (video)

Andreas Björklund (Lund, Sweden), Thore Husfeldt (Lund University and Basic Algorithms Research Copenhagen, ITU Copenhagen) and Petteri Kaski (Department of Computer Science, Aalto University, Espoo, Finland)

12:12

An area law for 2D frustration-free spin systems (video)

Anurag Anshu (Harvard University), Itai Arad (Technion) and David Gosset (University of Waterloo)

Expanders via Local Edge Flips in Quasilinear Time (video)

George Giakkoupis (Inria, Rennes, France)

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV (video)

Timothy M. Chan (UIUC), Virginia Vassilevska Williams (Massachusetts Institute of Technology) and Yinzhan Xu (Massachusetts Institute of Technology)

12:24

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture (video)

Sevag Gharibian (Paderborn University) and François Le Gall (Nagoya University)

(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics (video)

Zhihao Gavin Tang (Shanghai University of Finance and Economics), Jinzhao Wu (Peking University) and Hongxun Wu (Tsinghua University)

Edge Connectivity Augmentation in Near-Linear Time (video)

Ruoxu Cen (Duke University), Jason Li (UC Berkeley) and Debmalya Panigrahi (Duke University)

12:36

Near-Optimal Quantum Algorithms for Multivariate Mean Estimation (video)

Arjan Cornelissen (QuSoft, University of Amsterdam), Yassine Hamoudi (UC Berkeley) and Sofiene Jerbi (Institute for Theoretical Physics, University of Innsbruck)

The Power of Multiple Choices in Online Stochastic Matching (video)

Zhiyi Huang (The University of Hong Kong), Xinkai Shu (The University of Hong Kong) and Shuyi Yan (Tsinghua University)

Optimal Vertex Connectivity Oracles (video)

Seth Pettie (University of Michigan), Thatchaphol Saranurak (University of Michigan) and Longhui Yin (Tsinghua University)

12:48

Distributed quantum inner product estimation (video)

Anurag Anshu (Harvard University), Zeph Landau (UC Berkeley) and Yunchao Liu (UC Berkeley)

Online Edge Coloring via Tree Recurrences and Correlation Decay (video)

Janardhan Kulkarni (Microsoft), Yang P. Liu (Stanford University), Mehtaab Sawhney (MIT), Ashwin Sah (MIT) and Jakub Tarnawski (Microsoft)

Deterministic Massively Parallel Connectivity (video)

Sam Coy (University of Warwick) and Artur Czumaj (University of Warwick)

13:00

Break

Session #2: Monday, June 20, 13:30 UTC

Auditorium

2A: Pseudorandomness

Chair: Swastik Kopparty

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

2B: Streaming

Chair: Michael Kapralov

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

2C: Approximations

Chair: Anupam Gupta

Zoom: https://acm-org.zoom.us/j/2547463682

13:30

Hypercontractivity on High Dimensional Expanders (video)

Tom Gur (University of Warwick), Noam Lifshitz (Hebrew University of Jerusalem) and Siqi Liu (UC Berkeley)

New Streaming Algorithms for High Dimensional EMD and MST (video)

Xi Chen (Columbia), Rajesh Jayaram (Google Research), Amit Levi (University of Waterloo) and Erik Waingarten (Standford)

A PTAS for Unsplittable Flow on a Path (video)

Fabrizio Grandoni (IDSIA, USI-SUPSI), Tobias Mömke (University of Augsburg) and Andreas Wiese (Vrije Universiteit Amsterdam)

13:42

Hypercontractivity on High Dimensional Expanders (video)

Mitali Bafna (Harvard), Max Hopkins (UCSD), Tali Kaufman (Bar Ilan University) and Shachar Lovett (UCSD)

Brooks’ Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for ∆-Coloring (video)

Sepehr Assadi (Rutgers University), Pankaj Kumar (Charles University) and Parth Mittal (Rutgers University)

A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs (video)

Julia Chuzhoy (Toyota Technological Institute at Chicago) and Zihan Tan (University of Chicago)

13:54

Approximate Polymorphisms (video)

Gilad Chase (Technion - Israel Institute of Technology), Yuval Filmus (Technion - Israel Institute of Technology), Dor Minzer (MIT), Elchanan Mossel (MIT) and Nitin Saurabh (IIT Hyderabad)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $poly(1 / \varepsilon)$ Passes in the Semi-Streaming Model and Beyond (video)

Manuela Fischer (ETH Zurich), Slobodan Mitrović (UC Davis) and Jara Uitto (Aalto University)

Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios (video)

Matthias Englert (University of Warwick), Nicolaos Matsakis (Unaffiliated) and Pavel Veselý (Charles University)

14:06

Learning low-degree functions from a logarithmic number of random queries (video)

Alexandros Eskenazis (University of Cambridge) and Paata Ivanisvili (University of California, Irvine)

Deterministic Graph Coloring in the Streaming Model (video)

Sepehr Assadi (Rutgers University), Andrew Chen (Cornell University) and Glenn Sun (UCLA)

Flow Time Scheduling and Prefix Beck-Fiala (video)

Nikhil Bansal (University of Michigan), Lars Rohwedder (EPFL) and Ola Svensson (EPFL)

14:18

Positive spectrahedra: Invariance principles and Pseudorandom generators (video)

Srinivasan Arunachalam (IBM T. J. Watson Research Center) and Penghui Yao (Nanjing University)

Low-temperature Ising dynamics with random initializations (video)

Reza Gheissari (U.C. Berkeley) and Alistair Sinclair (U.C. Berkeley)

Bypassing the Surface Embedding: Approximation Schemes for Network Design in Minor-Free Graphs (video)

Vincent Cohen-Addad (Google Research, Switzerland)

14:30

Poster Session #1-2

15:30

Welcome reception

Tuesday, June 21

Auditorium

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

Zoom: https://acm-org.zoom.us/j/2547463682

Room Aula Magna DIAG

Zoom: https://acm-org.zoom.us/j/4770505040

7:00

Workshop #1: Methods, Challenges, and Applications of Constrained Graph Layouts – Planarity Always Strikes Back

Organizers: Patrizio Angelini (John Cabot University), Giordano Da Lozzo (Roma Tre University)

Workshop #2: Optimizing the Effort of Others: from algorithmic contracts to strategic classification

Organizers: Michal Feldman (Tel Aviv University & Microsoft Research), Brendan Lucier (Microsoft Research)

Workshop #3: The Multiple Facets of Quantum Proofs

Organizers: Alessandro Chiesa (UC Berkeley & EPFL), Tom Gur (University of Warwick), Dakshita Khurana (UIUC), Giulio Malavolta (Max Planck Institute), Thomas Vidick (Caltech)

Workshop #4: Algorithms with Predictions

Organizers: Piotr Indyk (MIT), Michael Mitzenmacher (Harvard), Sergei Vassilvitskii (Google)

8:30

Coffee break

9:00

Workshop (cont.)

10:15

Lunch

TCS Women Lunch

Room San Bernardino da Siena

STOC Best Paper Awardee Talks

Auditorium

Chair: Anupam Gupta

Zoom: https://acm-org.zoom.us/j/93405579312

12:00

Locally Testable Codes with constant rate, distance, and locality (video)

Irit Dinur (Weizmann), Shai Evra (Hebrew U), Ron Livne (Hebrew U), Alexander Lubotzky (Weizmann) and Shahar Mozes (Hebrew U)

12:22

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes (video)

Pavel Panteleev (Lomonosov Moscow State University) and Gleb Kalachev (Lomonosov Moscow State University)

12:45

Break

Session #3: Tuesday, June 21, 13:15 UTC

Auditorium

3A: Algebraic

Chair: Mika Goos

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

3B: Distributed

Chair: Eva Rotenberg

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

3C: Continuous

Chair: Jerry Li

Zoom: https://acm-org.zoom.us/j/2547463682

13:15

Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals (video)

Robert Andrews (University of Illinois at Urbana-Champaign) and Michael A. Forbes (University of Illinois at Urbana-Champaign)

Near-Optimal Distributed Degree+1 Coloring (video)

Magnus M. Halldorsson (Reykjavik University), Fabian Kuhn (University of Freiburg), Alexandre Nolin (Reykjavik University) and Tigran Tonoyan (Technion)

No self-concordant barrier interior point method is strongly polynomial (video)

Xavier Allamigeon (INRIA & Ecole Polytechnique), Stéphane Gaubert (INRIA & Ecole Polytechnique) and Nicolas Vandame (INRIA & Ecole Polytechnique)

13:27

Fast, algebraic multivariate multipoint evaluation in small characteristic and applications (video)

Vishwas Bhargava (Rutgers University), Sumanta Ghosh (IIT Bombay), Mrinal Kumar (IIT Bombay) and Chandra Kanta Mohapatra (IIT Bombay)

Distributed $\Delta$-Coloring Plays Hide-and-Seek (video)

Alkida Balliu (Gran Sasso Science Institute, Italy), Sebastian Brandt (CISPA Helmholtz Center for Information Security), Fabian Kuhn (University of Freiburg) and Dennis Olivetti (Gran Sasso Science Institute, Italy)

Improved Iteration Complexities for Overconstrained p-Norm Regression (video)

Arun Jambulapati (Stanford University), Yang P. Liu (Stanford University) and Aaron Sidford (Stanford University)

13:39

Set-multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication (video)

Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA), Nutan Limaye (ITU-Copenhagen) and Srikanth Srinivasan (Department of Mathematics, IIT Bombay)

Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms

Václav Rozhoň (ETH Zurich), Christoph Grunau (ETH Zurich), Bernhard Haeupler (ETH Zurich & Carnegie Mellon University), Goran Zuzic (ETH Zurich) and Jason Li (UC Berkeley)

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers (video)

Jan van den Brand (Simons Institute and UC Berkeley), Yu Gao (Georgia Institute of Technology), Arun Jambulapati (Stanford University), Yin Tat Lee (University of Washington), Yang P. Liu (Stanford University), Richard Peng (Georgia Institute of Technology) and Aaron Sidford (Stanford University)

13:51

Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs are not Unique Neighbor Expanders (video)

Amitay Kamber (University of Cambridge) and Tali Kaufman (Bar Ilan University)

Improved Communication Complexity of Fault-Tolerant Consensus

Jan Olkowski (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland) and Dariusz R. Kowalski (Augusta University, Augusta, Georgia)

Sparsified Block Elimination for Directed Laplacians (video)

Richard Peng (Georgia Tech) and Zhuoqing Song (Fudan University)

14:03

On the Complexity of CSP-based Ideal Membership Problems (video)

Andrei A. Bulatov (Simon Fraser University) and Akbar Rafiey (Simon Fraser University)

Byzantine Agreement in Polynomial Time with Near-Optimal Resilience (video)

Shang-En Huang (University of Michigan), Seth Pettie (University of Michigan) and Leqi Zhu (University of Michigan)

Matrix anti-concentration inequalities with applications (video)

Zipei Nie (Lagrange Mathematics and Computing Research Center)

14:15

Coffee break

Session #4: Tuesday, June 21, 14:45 UTC

Auditorium

4A: Coding etc.

Chair: Sam Hopkins

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

4B: Matrices etc

Chair: Kasper Green Larsen

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

4C: AGT

Chair: Brendan Lucier

Zoom: https://acm-org.zoom.us/j/2547463682

14:45

Circuits Resilient to Short-Circuit Errors (video)

Klim Efremenko (Ben Gurion University), Bernhard Haeupler (ETHZ & Carnegie Mellon University), Yael Tauman Kalai (Microsoft Research & MIT), Pritish Kamath (Google Research), Gillat Kol (Princeton University), Nicolas Resch (CWI) and Raghuvansh R. Saxena (Microsoft Research)

Matrix Discrepancy from Quantum Communication (video)

Sam Hopkins (UC Berkeley), Prasad Raghavendra (U.C. Berkeley) and Abhishek Shetty (UC Berkeley)

On the Hardness of Dominant Strategy Mechanism Design (video)

Shahar Dobzinski (Weizmann Institute of Science), Shiri Ron (Weizmann Institute of Science) and Jan Vondrak (Stanford)

14:57

Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet (video)

Inbar Ben Yaacov (Tel Aviv University), Gil Cohen (Tel Aviv University) and Tal Yankovitz (Tel Aviv University)

A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent (video)

Daniel Dadush (CWI Amsterdam), Haotian Jiang (University of Washington) and Victor Reis (University of Washington)

Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms (video)

Yang Cai (Yale University), Argyris Oikonomou (Yale University) and Mingfei Zhao (Google Research)

15:09

Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to $>\frac12$ Adversarial Corruption (video)

Rachel Yun Zhang (MIT), Meghal Gupta (Microsoft Research) and Yael Tauman Kalai (Microsoft Research)

Uniform Approximations for Randomized Hadamard Transforms with Applications (video)

Yeshwanth Cherapanamjeri (UC Berkeley) and Jelani Nelson (UC Berkeley)

Approximately Efficient Bilateral Trade (video)

Yuan Deng (Google Research), Jieming Mao (Google Research), Balasubramanian Sivan (Google Research) and Kangning Wang (Duke University)

15:21

The Query Complexity of Certification (video)

Guy Blanc (Stanford University), Caleb Koch (Stanford University), Jane Lange (MIT) and Li-Yang Tan (Stanford University)

Testing thresholds for high-dimensional sparse random geometric graphs (video)

Siqi Liu (UC Berkeley), Sidhanth Mohanty (UC Berkeley), Tselil Schramm (Stanford) and Elizabeth Yang (UC Berkeley)

Pricing Ordered Items (video)

Shuchi Chawla (UT Austin), Rojin Rezvan (UT Austin), Yifeng Teng (Google Research) and Christos Tzamos (University of Wisconsin-Madison)

15:33

Deniable Encryption in a Quantum World (video)

Andrea Coladangelo (Simons Institute for the Theory of Computing, UC Berkeley, qBraid), Shafi Goldwasser (Simons Institute for the Theory of Computing, UC Berkeley) and Umesh Vazirani (UC Berkeley)

Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random" (video)

Venkatesan Guruswami (Carnegie Mellon University), Pravesh K. Kothari (Carnegie Mellon University) and Peter Manohar (Carnegie Mellon University)

Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games (video)

Ioannis Anagnostides (Carnegie mellon university), Constantinos Daskalakis (Massachusetts Institute of Technology), Gabriele Farina (Carnegie Mellon University), Maxwell Fishelson (Massachusetts Institute of Technology), Noah Golowich (Massachusetts Institute of Technology) and Tuomas Sandholm (Carnegie Mellon University)

15:45

Poster Session #3-4 / Aperitifs

16:45

Amazon event

Room San Francesco

Zoom: https://acm-org.zoom.us/j/92135408181

Wednesday, June 22

Auditorium

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

Zoom: https://acm-org.zoom.us/j/2547463682

Room Aula Magna DIAG

Zoom: https://acm-org.zoom.us/j/4770505040

6:45

Workshop #6: Dynamic Algorithms: Recent Advances and Applications

Organizers: Sayan Bhattacharya (University of Warwick), Thatchaphol Saranurak (University of Michigan)

7:00

Workshop #2: Optimizing the Effort of Others: from algorithmic contracts to strategic classification

Organizers: Michal Feldman (Tel Aviv University & Microsoft Research), Brendan Lucier (Microsoft Research)

Workshop #5: Recent Advances in Coding Theory

Organizers: Noga Ron-Zewi (University of Haifa), Mary Wootters (Stanford University)

Workshop #1: Methods, Challenges, and Applications of Constrained Graph Layouts – Planarity Always Strikes Back

Organizers: Patrizio Angelini (John Cabot University), Giordano Da Lozzo (Roma Tre University)

8:30

Coffee break

9:00

Workshop (cont.)

10:15

Lunch

Junior-Senior Lunch

Room San Bernardino da Siena

Session #5: Wednesday, June 22, 11:30 UTC

Auditorium

5A: Quantum

Chair: Ronald de Wolf

Zoom: https://acm-org.zoom.us/j/8511501789

Room San Francesco

5B: Learning

Chair: Jerry Li

Zoom: https://acm-org.zoom.us/j/8828068524

Room Santa Chiara

5C: FPT

Chair: Euiwoong Lee

Zoom: https://acm-org.zoom.us/j/2547463682

11:30

Hamiltonian Complexity in the Thermodynamic Limit (video)

Dorit Aharonov (Hebrew University) and Sandy Irani (UC Irvine)

Reproducibility in Learning (video)

Russell Impagliazzo (UC San Diego), Rex Lei (UC San Diego), Toniann Pitassi (Columbia University) and Jessica Sorrell (UC San Diego)

Fast FPT-Approximation of Branchwidth (video)

Fedor V. Fomin (University of Bergen) and Tuukka Korhonen (University of Bergen)

11:42

Computational Complexity of the Ground State Energy Density Problem (video)

James D. Watson (University College London) and Toby S. Cubitt (University College London)

Kalman Filtering with Adversarial Corruptions (video)

Sitan Chen (UC Berkeley), Frederic Koehler (UC Berkeley), Ankur Moitra (Math & CSAIL, MIT) and Morris Yau (MIT)

Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion (video)

Bart M. P. Jansen (Eindhoven University of Technology) and Michał Włodarczyk (Eindhoven University of Technology)

11:54

Optimizing strongly interacting fermionic Hamiltonians (video)

Matthew B. Hastings (Microsoft Research) and Ryan O'Donnell (Carnegie Mellon University)

Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games (video)

Constantinos Daskalakis (EECS, MIT) and Noah Golowich (Google Research)

Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor (video)

Daniel Lokshtanov (University of California Santa Barbara, USA), Michał Pilipczuk (University of Warsaw), Marcin Pilipczuk (University of Warsaw) and Saket Saurabh (IMSc)

12:06

Public-Key Quantum Money with a Classical Bank

Omri Shmueli (Tel Aviv University)

Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster

Emmanuel Abbe (EPFL), Shuangping Li (Princeton University) and Allan Sly (Princeton University)

Twin-width IV: ordered graphs and matrices (video)

Édouard Bonnet (LIP, ENS Lyon), Ugo Giocanti (LIP, ENS Lyon), Patrice Ossona de Mendez (CAMS (CNRS, UMR 8557), Paris), Pierre Simon (UC Berkeley), Stéphan Thomassé (LIP, ENS Lyon) and Szymon Torunczyk (University of Warsaw)

12:18

Quantum Garbled Circuits (video)

Zvika Brakerski (Weizmann Institute) and Henry Yuen (Columbia University)

Learning General Halfspaces with General Massart Noise under the Gaussian Distribution (video)

Ilias Diakonikolas (UW Madison), Daniel M. Kane (University of California, San Diego), Vasilis Kontonis (UW Madison), Christos Tzamos (University of Wisconsin-Madison) and Nikos Zarifis (UW Madison)

Directed flow-augmentation (video)

Eun Jung Kim (Université Paris-Dauphine, PSL Research University, CNRS), Stefan Kratsch (Humboldt-Universität zu Berlin), Marcin Pilipczuk (University of Warsaw) and Magnus Wahlström (Royal Holloway, University of London)

12:45

Special Event with "Accademia Nazionale dei Lincei"

Keynote Speakers: Silvio Micali, Andrea Montanari, Giorgio Parisi, Patrick Hayden, and Umesh Vazirani

Location: Auditorium

Zoom: https://acm-org.zoom.us/j/96348065998

Session I. Chair: Stefano Leonardi