The times listed in this table are in Central European 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
08:45
TCS Women Spotlight Workshop
09: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)
10:30
Coffee break
11:00
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
12:15 Lunch
Student Lunch
Room San Bernardino da Siena and Jacopone da Todi
Session #1: Monday, June 20, 14:00 CET
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
14: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)
14: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)
14: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)
14: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)
14: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)
15:00
Break
Session #2: Monday, June 20, 15:30 CET
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
15: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)
15: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)
15: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)
16: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)
16: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)
16:30 Poster Session #1-2
17: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
09: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)
10:30
Coffee break
11:00
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
12: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
14: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)
14:22
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes (video)
Pavel Panteleev (Lomonosov Moscow State University) and Gleb Kalachev (Lomonosov Moscow State University)
14:45
Break
Session #3: Tuesday, June 21, 15:15 CET
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
15: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)
15: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)
15: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)
15: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)
16: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)
16:15
Coffee break
Session #4: Tuesday, June 21, 16:45 CET
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
16: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)
16: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)
17: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)
17: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)
17: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)
17:45 Poster Session #3-4 / Aperitifs
18: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
08:45
Workshop #6: Dynamic Algorithms: Recent Advances and Applications
Organizers: Sayan Bhattacharya (University of Warwick), Thatchaphol Saranurak (University of Michigan)
09: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)
10:30
Coffee break
11:00
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
12:15 Lunch Junior-Senior Lunch
Room San Bernardino da Siena
Session #5: Wednesday, June 22, 13:30 CET
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
13: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)
13: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)
13: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)
14: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)
14: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)
14: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
14:45
Giorgio Parisi (Accademia Nazionale dei Lincei and Sapienza University of Rome): Spin Glass Theory
15:20
Andrea Montanari (Stanford University): Algorithmic Spin Glass Theory
15:55
Coffee break
Session II. Chair: James Lee
16:25
Silvio Micali (MIT and Algorand): We, The People, Agree
17:00
Patrick Hayden (Stanford University): Navigating in a maelstrom: complexity and the structure of spacetime
17:35
Umesh Vazirani (Berkeley University): Testing quantum computers and quantum mechanics
18:15
Travel time
19:15 Reception
Location: Accademia Nazionale dei Lincei, Palazzo Corsini
21:15 Concert (tickets required)
Location: Botanical Garden of Rome
Thursday, June 23
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
08:45
Workshop #6: Dynamic Algorithms: Recent Advances and Applications
Organizers: Sayan Bhattacharya (University of Warwick), Thatchaphol Saranurak (University of Michigan)
09:00
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)
Workshop #5: Recent Advances in Coding Theory
Organizers: Noga Ron-Zewi (University of Haifa), Mary Wootters (Stanford University)
10:30
Coffee break
11:00
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
12:15 Lunch Senior-Junior Lunch
Room San Bernardino da Siena
STOC Best Student Paper Awardee Talks
Auditorium
Chair: Anupam Gupta
Zoom: https://acm-org.zoom.us/j/97735894739
14:00
The Optimal Error Resilience of Interactive Communication Over Binary Channels (video)
Rachel Yun Zhang (MIT) and Meghal Gupta (Microsoft Research)
14:22
The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity (video)
Zhiyuan Fan (Tsinghua University), Jiatu Li (Tsinghua University) and Tianqi Yang (Tsinghua University)
14:45
Break
Session #6: Thursday, June 23, 15:15 CET
Auditorium
6A: CSPs etc.
Chair: Ryan Williams
Zoom: https://acm-org.zoom.us/j/8511501789
Room San Francesco
6B: Geometry/Metrics
Chair: Anupam Gupta
Zoom: https://acm-org.zoom.us/j/8828068524
Room Santa Chiara
6C: Sublinear
Chair: Michael Kapralov
Zoom: https://acm-org.zoom.us/j/2547463682
15:15
On Approximability of Satisfiable $k$-CSPs: I (video)
Amey Bhangale (University of California, Riverside), Subhash Khot (New York University) and Dor Minzer (Massachusetts Institute of Technology)
Towards Optimal Lower Bounds for k-median and k-means Coresets (video)
Vincent Cohen-Addad (Google Research, Switzerland), Kasper Green Larsen (Aarhus University), David Saulpic (Sorbonne Université) and Chris Schwiegelshohn (Aarhus University)
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime (video)
Karl Bringmann (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany), Alejandro Cassis (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany), Nick Fischer (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany) and Vasileios Nakos (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany)
15:27
A Characterization of Approximability for Biased CSPs (video)
Euiwoong Lee (University of Michigan) and Suprovat Ghoshal (Indian Institute of Science, Bangalore)
Deterministic, Near-Linear $\varepsilon$-Approximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal (Duke University), Hsien-Chih Chang (Department of Computer Science, Dartmouth College), Sharath Raghvendra (Virginia Tech) and Allen Xiao (Duke University)
Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses (video)
Jakub Tětek (Basic Algorithms Research Copenhagen, University of Copenhagen) and Mikkel Thorup (University of Copenhagen)
15:39
Parallel Repetition For All 3-Player Games Over Binary Alphabet (video)
Uma Girish (Princeton University), Justin Holmgren (NTT Research), Kunal Mittal (Princeton University), Ran Raz (Princeton University) and Wei Zhan (Princeton University)
Locality-Sensitive Orderings and Applications to Reliable Spanners (video)
Arnold Filtser (Bar-Ilan University) and Hung Le (University of Massachusetts Amherst)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products (video)
Ainesh Bakshi (Carnegie Mellon University), Ken Clarkson (IBM Research) and David P. Woodruff (Carnegie Mellon University)
15:51
Constant Inapproximability for PPA (video)
Argyrios Deligkas (Royal Holloway, University of London), John Fearnley (University of Liverpool), Alexandros Hollender (University of Oxford) and Themistoklis Melissourgos (Technical University of Munich)
Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed and Parallel
Merav Parter (Weizmann IS)
Sublinear Time Spectral Density Estimation (video)
Aditya Krishnan (Johns Hopkins University), Vladimir Braverman (Johns Hopkins University, Google) and Christopher Musco (New York University)
16:03
Complexity classification of counting graph homomorphisms modulo a prime number (video)
Andrei Bulatov (Simon Fraser University) and Amirhossein Kazeminia (Simon Fraser University)
Maintaining Exact Distances under Multiple Edge Failures (video)
Ran Duan (Tsinghua University) and Hanlin Ren (University of Oxford)
Memory Bounds for the Experts Problem (video)
Vaidehi Srinivas (Northwestern University), David P. Woodruff (Carnegie Mellon University), Ziyu Xu (Carnegie Mellon University) and Samson Zhou (Carnegie Mellon University)
16:15
Coffee break
Session #7: Thursday, June 23, 16:45 CET
Auditorium
7A: Complexity
Chair: Mika Goos
Zoom: https://acm-org.zoom.us/j/8511501789
Room San Francesco
7B: Learning
Chair: Luca Trevisan
Zoom: https://acm-org.zoom.us/j/8828068524
Room Santa Chiara
7C: Data Structures
Chair: Eva Rotenberg
Zoom: https://acm-org.zoom.us/j/2547463682
16:45
A strong version of Cobham's theorem (video)
Philipp Hieronymi (Universität Bonn) and Christian Schulz (University of Illinois)
Robustly Learning Mixtures of $k$ Arbitrary Gaussians (video)
Ainesh Bakshi (Carnegie Mellon University), Ilias Diakonikolas (UW Madison), He Jia (Georgia Tech), Daniel M. Kane (University of California, San Diego), Pravesh K. Kothari (Carnegie Mellon University) and Santosh S. Vempala (Georgia Tech)
On the Optimal Time/Space Tradeoff for Hash Tables (video)
Michael Bender (Stony Brook University), Martin Farach-Colton (Rutgers University), John Kuszmaul (Yale University), William Kuszmaul (MIT) and Mingmou Liu (Nanyang Technological University)
16:57
3.1n − o(n) Circuit Lower Bounds for Explicit Functions (video)
Jiatu Li (Tsinghua University) and Tianqi Yang (Tsinghua University)
Clustering Mixtures with Almost Optimal Separation in Polynomial Time (video)
Allen Liu (MIT) and Jerry Li (Microsoft Research)
An extendable data structure for incremental stable perfect hashing (video)
Ioana Bercea (IT University of Copenhagen) and Guy Even (Tel-Aviv University)
17:09
The Approximate Degree of DNF and CNF Formulas (video)
Alexander Sherstov (University of California, Los Angeles)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation (video)
Ilias Diakonikolas (UW Madison), Daniel Kane (UCSD), Daniel Kongsgaard (University of California, San Diego), Jerry Li (Microsoft Research) and Kevin Tian (Stanford University)
Almost-Linear ε-Emulators for Planar Graphs (video)
Hsien-Chih Chang (Dartmouth College), Robert Krauthgamer (Weizmann Institute of Science) and Zihan Tan (The University of Chicago)
17:21
Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties (video)
Tal Herman (Weizmann Institute of Science) and Guy Rothblum (Weizmann Institute of Science)
List-Decodable Covariance Estimation (video)
Misha Ivkov (CMU) and Pravesh K. Kothari (CMU)
Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
Mohsen Ghaffari (ETH Zurich), Bernhard Haeupler (Carnegie Mellon University & ETH Zurich) and Harald Räcke (Technical University Munich)
17:33
Randomized Communication and Implicit Graph Representations (video)
Nathaniel Harms (University of Waterloo), Sebastian Wild (University of Liverpool, UK) and Viktor Zamaraev (University of Liverpool, UK)
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism (video)
Sam Hopkins (UC Berkeley), Gautam Kamath (University of Waterloo) and Mahbod Majid (University of Waterloo)
Optimal Oblivious Reconfigurable Networks (video)
Daniel Amir (Cornell University), Tegan Wilson (Cornell University), Vishal Shrivastav (Purdue University), Hakim Weatherspoon (Cornell University), Robert Kleinberg (Cornell University) and Rachit Agarwal (Cornell University)
17:45 Poster Session #5-6-7 / Aperitifs
18:45
Business meeting
Auditorium
Zoom: https://acm-org.zoom.us/j/8511501789
Friday, June 24
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
08:45
Workshop #6: Dynamic Algorithms: Recent Advances and Applications
Organizers: Sayan Bhattacharya (University of Warwick), Thatchaphol Saranurak (University of Michigan)
09:00
Workshop #4: Algorithms with Predictions
Organizers: Piotr Indyk (MIT), Michael Mitzenmacher (Harvard), Sergei Vassilvitskii (Google)
Workshop #5: Recent Advances in Coding Theory
Organizers: Noga Ron-Zewi (University of Haifa), Mary Wootters (Stanford University)
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)
10:30
Coffee break
11:00
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
Workshop (cont.)
12:15 Lunch
14:00
Invited talk: Claire Mathieu (CNRS, Paris): Pandemic Models
Chair: Anupam Gupta
Auditorium
Zoom: https://acm-org.zoom.us/j/93584046994
Session #8: Friday, June 24, 14:45 CET
Auditorium
8A: Crypto/Coding
Chair: Ryan Williams
Zoom: https://acm-org.zoom.us/j/8511501789
Room San Francesco
8B: MCMC
Chair: Jerry Li
Zoom: https://acm-org.zoom.us/j/8828068524
Room Santa Chiara
8C: Fine-grained
Chair: Karl Bringmann
Zoom: https://acm-org.zoom.us/j/2547463682
14:45
Linear Space Streaming Lower Bounds for Approximating CSPs (video)
Chi-Ning Chou (Harvard University), Alexander Golovnev (Georgetown University), Madhu Sudan (Harvard University), Ameya Velingker (Google Research) and Santhoshini Velusamy (Harvard University)
Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models (video)
Nima Anari (Stanford University), Vishesh Jain (Stanford University), Frederic Koehler (UC Berkeley), Huy Tuan Pham (Stanford University) and Thuy-Duong Vuong (Stanford University)
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond (video)
Amir Abboud (Weizmann Institute of Science), Karl Bringmann (Saarland University), Seri Khoury (UC Berkeley) and Or Zamir (Institute for Advanced Study)
14:57
Rate One-Third Non-malleable Codes (video)
Divesh Aggarwal (National University of Singapore), Sruthi Sekar (UC Berkeley, California), Bhavana Kanukurthi (Indian Institute of Science Bangalore), Maciej Obremski (National University of Singapore) and Sai Lakshmi Bhavana Obbattu (Microsoft Research, Bangalore)
Simple Parallel Algorithms for Single-Site Dynamics (video)
Hongyang Liu (Nanjing University) and Yitong Yin (Nanjing University)
Breaking the $n^k$ Barrier for Minimum $k$-cut on Simple Graphs (video)
Zhiyang He (MIT) and Jason Li (UC Berkeley)
15:09
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead (video)
Noga Ron-Zewi (University of Haifa) and Ron Rothblum (Technion)
Computational thresholds for the fixed-magnetization Ising model (video)
Charlie Carlson (University of Colorado Boulder), Ewan Davies (University of Colorado Boulder), Alexandra Kolla (University of Colorado Boulder) and Will Perkins (University of Illinois at Chicago)
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv (video)
Ce Jin (MIT) and Yinzhan Xu (MIT)
15:21
On the Complexity of Two-Party Differential Privacy (video)
Iftach Haitner (Tel Aviv University), Noam Mazor (Tel Aviv University), Jad Silbak (Tel Aviv University) and Eliad Tsfadia (Tel Aviv University)
Approximate counting and sampling via local central limit theorems (video)
Vishesh Jain (Stanford University), Will Perkins (UIC), Ashwin Sah (MIT) and Mehtaab Sawhney (MIT)
Faster Min-Plus Product for Monotone Instances (video)
Shucheng Chi (Tsinghua University), Ran Duan (Tsinghua University), Tianle Xie (Tsinghua University) and Tianyi Zhang (Tel Aviv University)
15:33
Counting Small Induced Subgraphs with Hereditary Properties (video)
Jacob Focke (CISPA Helmholtz Center for Information Security) and Marc Roth (University of Oxford)
14:45
Break
Session #9: Friday, June 24, 16:15 CET
Auditorium
9A: Pseudorandomness
Chair: Luca Trevisan
Zoom: https://acm-org.zoom.us/j/8511501789
Room San Francesco
9B: Approximation
Chair: Euiwoong Lee
Zoom: https://acm-org.zoom.us/j/8828068524
Room Santa Chiara
9C: Dynamic
Chair: Thatchaphol Saranurak
Zoom: https://acm-org.zoom.us/j/2547463682
16:15
Pseudodeterminism: Promises and Lowerbounds (video)
Peter Dixon (Iowa State University), A. Pavan (Iowa State University), Jason Vander Woude (University of Nebraska-Lincoln) and N. V. Vinodchandran (University of Nebraska-Lincoln)
Breaching the 2-Approximation Barrier for the Forest Augmentation Problem (video)
Fabrizio Grandoni (IDSIA, USI-SUPSI), Afrouz Jabal Ameli (IDSIA, USI-SUPSI) and Vera Traub (ETH Zurich)
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary (video)
Adam Karczmarz (University of Warsaw and IDEAS NCBR), Anish Mukherjee (University of Warsaw and IDEAS NCBR) and Piotr Sankowski (University of Warsaw and IDEAS NCBR)
16:27
Worst-Case to Average-Case Reductions via Additive Combinatorics (video)
Vahid R. Asadi (University of Waterloo), Alexander Golovnev (Harvard University), Tom Gur (University of Warwick) and Igor Shinkar (Simon Fraser University)
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem (video)
Anna Karlin (University of Washington), Nathan Klein (University of Washington), Shayan Oveis Gharan (University of Washington) and Xinzhi Zhang (University of Washington)
Dynamic Suffix Array with Polylogarithmic Queries and Updates (video)
Dominik Kempa (Stony Brook University) and Tomasz Kociumaka (UC Berkeley)
16:39
Robustness of Average-Case Meta-Complexity via Pseudorandomness
Rahul Ilango (MIT), Hanlin Ren (Oxford University) and Rahul Santhanam (Oxford University)
Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets (video)
Vincent Cohen-Addad (Google), Hossein Esfandiari (Google), Vahab Mirrokni (Google Research) and Shyam Narayanan (Massachusetts Institute of Technology)
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds (video)
Amos Beimel (Ben-Gurion University), Haim Kaplan (Tel Aviv University and Google research), Yishay Mansour (Tel Aviv University and Google research), Kobbi Nissim (Georgetown University), Thatchaphol Saranurak (University of Michigan) and Uri Stemmer (Tel Aviv University and Google research)
16:51
Extractors for Sum of Two Sources (video)
Eshan Chattopadhyay (Cornell University) and Jyun-Jie Liao (Cornell University)
Explainable k-means. Don’t be greedy, plant bigger trees! (video)
Konstantin Makarychev (Northwestern University) and Liren Shan (Northwestern University)
On the Complexity of Dynamic Submodular Maximization (video)
Binghui Peng (Columbia University) and Xi Chen (Columbia University)
17:05 Poster Session #8-9
The times listed in this table are in Central European Time.