STOC 2022 – Proceedings

Frontmatter

Session 1A

Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen
(Columbia University, USA; University of Maryland, USA)

Publisher's Version Article: stoc22main-p12-p doi:10.1145/3519935.3519949

An Area Law for 2D Frustration-Free Spin Systems
Anurag Anshu, Itai Arad, and David Gosset
(Harvard University, USA; Technion, Israel; University of Waterloo, Canada)

Publisher's Version Article: stoc22main-p73-p doi:10.1145/3519935.3519962

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
Sevag Gharibian and François Le Gall
(Paderborn University, Germany; Nagoya University, Japan)

Publisher's Version Article: stoc22main-p215-p doi:10.1145/3519935.3519991

Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi
(University of Amsterdam, Netherlands; University of California at Berkeley, USA; University of Innsbruck, Austria)

Publisher's Version Article: stoc22main-p603-p doi:10.1145/3519935.3520045

Distributed Quantum Inner Product Estimation
Anurag Anshu, Zeph Landau, and Yunchao Liu
(Harvard University, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p143-p doi:10.1145/3519935.3519974

Session 1B

The Power of Two Choices in Graphical Allocation
Nikhil Bansal and Ohad N. Feldheim
(University of Michigan, USA; Hebrew University of Jerusalem, Israel)

Publisher's Version Article: stoc22main-p227-p doi:10.1145/3519935.3519995

Expanders via Local Edge Flips in Quasilinear Time
George Giakkoupis
(Inria, France; University of Rennes, France; CNRS, France; IRISA, France)

Publisher's Version Article: stoc22main-p381-p doi:10.1145/3519935.3520022

(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu
(Shanghai University of Finance and Economics, China; Peking University, China; Tsinghua University, China)

Publisher's Version Article: stoc22main-p226-p doi:10.1145/3519935.3519994

The Power of Multiple Choices in Online Stochastic Matching
Zhiyi Huang, Xinkai Shu, and Shuyi Yan
(University of Hong Kong, China; Tsinghua University, China)

Publisher's Version Article: stoc22main-p622-p doi:10.1145/3519935.3520046

Online Edge Coloring via Tree Recurrences and Correlation Decay
Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski
(Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p175-p doi:10.1145/3519935.3519986

Session 1C

The Shortest Even Cycle Problem Is Tractable
Andreas Björklund, Thore Husfeldt, and Petteri Kaski
(Lund University, Sweden; IT University of Copenhagen, Denmark; Aalto University, Finland)

Publisher's Version Article: stoc22main-p454-p doi:10.1145/3519935.3520030

Breaking the n^k Barrier for Minimum k-Cut on Simple Graphs
Zhiyang He and Jason Li
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p7-p doi:10.1145/3519935.3519948

Edge Connectivity Augmentation in Near-Linear Time
Ruoxu Cen, Jason Li, and Debmalya Panigrahi
(Duke University, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p528-p doi:10.1145/3519935.3520038

Optimal Vertex Connectivity Oracles
Seth Pettie, Thatchaphol Saranurak, and Longhui Yin
(University of Michigan, USA; Tsinghua University, China)

Publisher's Version Article: stoc22main-p3-p doi:10.1145/3519935.3519945

Deterministic Massively Parallel Connectivity
Sam Coy and Artur Czumaj
(University of Warwick, UK)

Publisher's Version Article: stoc22main-p670-p doi:10.1145/3519935.3520055

Session 2A

Hypercontractivity on High Dimensional Expanders
Tom Gur, Noam Lifshitz, and Siqi Liu
(University of Warwick, UK; Hebrew University of Jerusalem, Israel; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p268-p doi:10.1145/3519935.3520004

Hypercontractivity on High Dimensional Expanders
Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett
(Harvard University, USA; University of California at San Diego, USA; Bar-Ilan University, Israel)

Publisher's Version Article: stoc22main-p557-p doi:10.1145/3519935.3520040

Approximate Polymorphisms
Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh
(Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India)

Publisher's Version Article: stoc22main-p94-p doi:10.1145/3519935.3519966

Learning Low-Degree Functions from a Logarithmic Number of Random Queries
Alexandros Eskenazis and Paata Ivanisvili
(University of Cambridge, UK; University of California at Irvine, USA)

Publisher's Version Article: stoc22main-p165-p doi:10.1145/3519935.3519981

Positive Spectrahedra: Invariance Principles and Pseudorandom Generators
Srinivasan Arunachalam and Penghui Yao
(IBM Research, USA; Nanjing University, China)

Publisher's Version Article: stoc22main-p92-p doi:10.1145/3519935.3519965

Session 2B

New Streaming Algorithms for High Dimensional EMD and MST
Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten
(Columbia University, USA; Google Research, USA; University of Waterloo, Canada; Stanford University, USA)

Publisher's Version Article: stoc22main-p160-p doi:10.1145/3519935.3519979

Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring
Sepehr Assadi, Pankaj Kumar, and Parth Mittal
(Rutgers University, USA; Charles University in Prague, Czechia)

Publisher's Version Article: stoc22main-p271-p doi:10.1145/3519935.3520005

Deterministic (1+𝜀)-Approximate Maximum Matching with poly(1/𝜀) Passes in the Semi-streaming Model and Beyond
Manuela Fischer, Slobodan Mitrović, and Jara Uitto
(ETH Zurich, Switzerland; University of California at Davis, USA; Aalto University, Finland)

Publisher's Version Article: stoc22main-p539-p doi:10.1145/3519935.3520039

Deterministic Graph Coloring in the Streaming Model
Sepehr Assadi, Andrew Chen, and Glenn Sun
(Rutgers University, USA; Cornell University, USA; University of California at Los Angeles, USA)

Publisher's Version Article: stoc22main-p343-p doi:10.1145/3519935.3520016

Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy
(Harvard University, USA; Georgetown University, USA; Google Research, USA)

Publisher's Version Article: stoc22main-p168-p doi:10.1145/3519935.3519983

Session 2C

A PTAS for Unsplittable Flow on a Path
Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese
(USI-SUPSI, Switzerland; University of Augsburg, Germany; Vrije Universiteit Amsterdam, Netherlands)

Publisher's Version Article: stoc22main-p59-p doi:10.1145/3519935.3519959

A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy and Zihan Tan
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)

Publisher's Version Article: stoc22main-p169-p doi:10.1145/3519935.3519984

Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
Matthias Englert, Nicolaos Matsakis, and Pavel Veselý
(University of Warwick, UK; Charles University in Prague, Czechia)

Publisher's Version Article: stoc22main-p258-p doi:10.1145/3519935.3520001

Flow Time Scheduling and Prefix Beck-Fiala
Nikhil Bansal, Lars Rohwedder, and Ola Svensson
(University of Michigan, USA; Maastricht University, Netherlands; EPFL, Switzerland)

Publisher's Version Article: stoc22main-p1200-p doi:10.1145/3519935.3520077

Bypassing the Surface Embedding: Approximation Schemes for Network Design in Minor-Free Graphs
Vincent Cohen-Addad
(Google Research, Switzerland)

Publisher's Version Article: stoc22main-p637-p doi:10.1145/3519935.3520049

Award Papers Session I: Best Papers

Locally Testable Codes with Constant Rate, Distance, and Locality
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes
(Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)

Publisher's Version Article: stoc22main-p391-p doi:10.1145/3519935.3520024

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes
Pavel Panteleev and Gleb Kalachev
(Lomonosov Moscow State University, Russia)

Publisher's Version Article: stoc22main-p353-p doi:10.1145/3519935.3520017

Session 3A

Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals
Robert Andrews and Michael A. Forbes
(University of Illinois at Urbana-Champaign, USA)

Publisher's Version Article: stoc22main-p404-p doi:10.1145/3519935.3520025

Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications
Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra
(Rutgers University, USA; California Institute of Technology, USA; IIT Bombay, India)

Publisher's Version Article: stoc22main-p108-p doi:10.1145/3519935.3519968

Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication
Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan
(Université Grenoble Alpes, France; Université Savoie Mont Blanc, France; CNRS, France; LAMA, France; IT University of Copenhagen, Denmark; Aarhus University, Denmark)

Publisher's Version Article: stoc22main-p600-p doi:10.1145/3519935.3520044

Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs Are Not Unique Neighbor Expanders
Amitay Kamber and Tali Kaufman
(University of Cambridge, UK; Bar-Ilan University, Israel)

Publisher's Version Article: stoc22main-p218-p doi:10.1145/3519935.3519992

On the Complexity of CSP-Based Ideal Membership Problems
Andrei A. Bulatov and Akbar Rafiey
(Simon Fraser University, Canada)

Publisher's Version Article: stoc22main-p784-p doi:10.1145/3519935.3520063

Session 3B

Near-Optimal Distributed Degree+1 Coloring
Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan
(Reykjavik University, Iceland; University of Freiburg, Germany; Krisp Technologies, Armenia)

Publisher's Version Article: stoc22main-p388-p doi:10.1145/3519935.3520023

Distributed ∆-Coloring Plays Hide-and-Seek
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti
(Gran Sasso Science Institute, Italy; CISPA, Germany; University of Freiburg, Germany)

Publisher's Version Article: stoc22main-p425-p doi:10.1145/3519935.3520027

Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms
Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p1051-p doi:10.1145/3519935.3520074

Improved Communication Complexity of Fault-Tolerant Consensus
Mohammad T. Hajiaghayi, Dariusz R. Kowalski, and Jan Olkowski
(University of Maryland, USA; Augusta University, USA)

Publisher's Version Article: stoc22main-p1242-p doi:10.1145/3519935.3520078

Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang, Seth Pettie, and Leqi Zhu
(University of Michigan, USA)

Publisher's Version Article: stoc22main-p341-p doi:10.1145/3519935.3520015

Session 3C

No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial
Xavier Allamigeon, Stéphane Gaubert, and Nicolas Vandame
(Inria, France; École Polytechnique, France; CNRS, France)

Publisher's Version Article: stoc22main-p236-p doi:10.1145/3519935.3519997

Improved Iteration Complexities for Overconstrained p-Norm Regression
Arun Jambulapati, Yang P. Liu, and Aaron Sidford
(Stanford University, USA)

Publisher's Version Article: stoc22main-p120-p doi:10.1145/3519935.3519971

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford
(Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA)

Publisher's Version Article: stoc22main-p885-p doi:10.1145/3519935.3520068

Sparsified Block Elimination for Directed Laplacians
Richard Peng and Zhuoqing Song
(University of Waterloo, Canada; Fudan University, China)

Publisher's Version Article: stoc22main-p654-p doi:10.1145/3519935.3520053

Matrix Anti-concentration Inequalities with Applications
Zipei Nie
(Huawei, France)

Publisher's Version Article: stoc22main-p755-p doi:10.1145/3519935.3520060

Session 4A

Circuits Resilient to Short-Circuit Errors
Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands)

Publisher's Version Article: stoc22main-p281-p doi:10.1145/3519935.3520007

Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet
Inbar Ben Yaacov, Gil Cohen, and Tal Yankovitz
(Tel Aviv University, Israel)

Publisher's Version Article: stoc22main-p495-p doi:10.1145/3519935.3520033

Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption
Meghal Gupta, Yael Tauman Kalai, and Rachel Yun Zhang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p161-p doi:10.1145/3519935.3519980

The Query Complexity of Certification
Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan
(Stanford University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p225-p doi:10.1145/3519935.3519993

Session 4B

Matrix Discrepancy from Quantum Communication
Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p31-p doi:10.1145/3519935.3519954

A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
Daniel Dadush, Haotian Jiang, and Victor Reis
(CWI, Netherlands; University of Washington, USA)

Publisher's Version Article: stoc22main-p101-p doi:10.1145/3519935.3519967

Uniform Approximations for Randomized Hadamard Transforms with Applications
Yeshwanth Cherapanamjeri and Jelani Nelson
(University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p69-p doi:10.1145/3519935.3519961

Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs
Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang
(University of California at Berkeley, USA; Stanford University, USA)

Publisher's Version Article: stoc22main-p198-p doi:10.1145/3519935.3519989

Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random
Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar
(University of California at Berkeley, USA; Carnegie Mellon University, USA)

Publisher's Version Article: stoc22main-p37-p doi:10.1145/3519935.3519955

Session 4C

On the Hardness of Dominant Strategy Mechanism Design
Shahar Dobzinski, Shiri Ron, and Jan Vondrák
(Weizmann Institute of Science, Israel; Stanford University, USA)

Publisher's Version Article: stoc22main-p332-p doi:10.1145/3519935.3520013

Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms
Yang Cai, Argyris Oikonomou, and Mingfei Zhao
(Yale University, USA; Google Research, USA)

Publisher's Version Article: stoc22main-p446-p doi:10.1145/3519935.3520029

Approximately Efficient Bilateral Trade
Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang
(Google Research, USA; Duke University, USA)

Publisher's Version Article: stoc22main-p665-p doi:10.1145/3519935.3520054

Pricing Ordered Items
Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos
(University of Texas at Austin, USA; Google Research, USA; University of Wisconsin-Madison, USA)

Publisher's Version Article: stoc22main-p797-p doi:10.1145/3519935.3520065

Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p474-p doi:10.1145/3519935.3520031

Session 5A

Hamiltonian Complexity in the Thermodynamic Limit
Dorit Aharonov and Sandy Irani
(Hebrew University of Jerusalem, Israel; University of California at Irvine, USA)

Publisher's Version Article: stoc22main-p858-p doi:10.1145/3519935.3520067

Computational Complexity of the Ground State Energy Density Problem
James D. Watson and Toby S. Cubitt
(University College London, UK)

Publisher's Version Article: stoc22main-p647-p doi:10.1145/3519935.3520052

Optimizing Strongly Interacting Fermionic Hamiltonians
Matthew B. Hastings and Ryan O'Donnell
(Microsoft, USA; Carnegie Mellon University, USA)

Publisher's Version Article: stoc22main-p64-p doi:10.1145/3519935.3519960

Public-Key Quantum Money with a Classical Bank
Omri Shmueli
(Tel Aviv University, Israel)

Publisher's Version Article: stoc22main-p23-p doi:10.1145/3519935.3519952

Quantum Garbled Circuits
Zvika Brakerski and Henry Yuen
(Weizmann Institute of Science, Israel; Columbia University, USA)

Publisher's Version Article: stoc22main-p1005-p doi:10.1145/3519935.3520073

Session 5B

Reproducibility in Learning
Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell
(University of California at San Diego, USA; Columbia University, USA)

Publisher's Version Article: stoc22main-p142-p doi:10.1145/3519935.3519973

Kalman Filtering with Adversarial Corruptions
Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau
(University of California at Berkeley, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p640-p doi:10.1145/3519935.3520050

Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games
Constantinos Daskalakis and Noah Golowich
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p15-p doi:10.1145/3519935.3519950

Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster
Emmanuel Abbe, Shuangping Li, and Allan Sly
(EPFL, Switzerland; Princeton University, USA)

Publisher's Version Article: stoc22main-p150-p doi:10.1145/3519935.3519975

Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)

Publisher's Version Article: stoc22main-p116-p doi:10.1145/3519935.3519970

Session 5C

Fast FPT-Approximation of Branchwidth
Fedor V. Fomin and Tuukka Korhonen
(University of Bergen, Norway)

Publisher's Version Article: stoc22main-p232-p doi:10.1145/3519935.3519996

Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
Bart M. P. Jansen and Michał Włodarczyk
(Eindhoven University of Technology, Netherlands)

Publisher's Version Article: stoc22main-p372-p doi:10.1145/3519935.3520021

Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh
(University of California at Santa Barbara, USA; University of Warsaw, Poland; IMSc, India; University of Bergen, Norway)

Publisher's Version Article: stoc22main-p1092-p doi:10.1145/3519935.3520076

Twin-Width IV: Ordered Graphs and Matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk
(LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland)

Publisher's Version Article: stoc22main-p523-p doi:10.1145/3519935.3520037

Directed Flow-Augmentation
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström
(Université Paris-Dauphine, France; PSL Research University, France; CNRS, France; Humboldt University of Berlin, Germany; University of Warsaw, Poland; Royal Holloway University of London, UK)

Publisher's Version Article: stoc22main-p361-p doi:10.1145/3519935.3520018

Award Papers Session II: Best Student Papers

The Optimal Error Resilience of Interactive Communication over Binary Channels
Meghal Gupta and Rachel Yun Zhang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p170-p doi:10.1145/3519935.3519985

The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity
Zhiyuan Fan, Jiatu Li, and Tianqi Yang
(Tsinghua University, China)

Publisher's Version Article: stoc22main-p298-p doi:10.1145/3519935.3520010

Session 6A

On Approximability of Satisfiable k-CSPs: I
Amey Bhangale, Subhash Khot, and Dor Minzer
(University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p439-p doi:10.1145/3519935.3520028

A Characterization of Approximability for Biased CSPs
Euiwoong Lee and Suprovat Ghoshal
(University of Michigan, USA)

Publisher's Version Article: stoc22main-p987-p doi:10.1145/3519935.3520072

Parallel Repetition for All 3-Player Games over Binary Alphabet
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan
(Princeton University, USA; NTT Research, USA)

Publisher's Version Article: stoc22main-p966-p doi:10.1145/3519935.3520071

Constant Inapproximability for PPA
Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos
(Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK)

Publisher's Version Article: stoc22main-p1379-p doi:10.1145/3519935.3520079

Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number
Andrei A. Bulatov and Amirhossein Kazeminia
(Simon Fraser University, Canada)

Publisher's Version Article: stoc22main-p1075-p doi:10.1145/3519935.3520075

Session 6B

Towards Optimal Lower Bounds for k-Median and k-Means Coresets
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn
(Google Research, Switzerland; Aarhus University, Denmark; Sorbonne University, France)

Publisher's Version Article: stoc22main-p4-p doi:10.1145/3519935.3519946

Deterministic, Near-Linear 𝜀-Approximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao
(Duke University, USA; Dartmouth College, USA; Virginia Tech, USA)

Publisher's Version Article: stoc22main-p153-p doi:10.1145/3519935.3519977

Locality-Sensitive Orderings and Applications to Reliable Spanners
Arnold Filtser and Hung Le
(Bar-Ilan University, Israel; University of Massachusetts at Amherst, USA)

Publisher's Version Article: stoc22main-p563-p doi:10.1145/3519935.3520042

Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed, and Parallel
Merav Parter
(Weizmann Institute of Science, Israel)

Publisher's Version Article: stoc22main-p625-p doi:10.1145/3519935.3520047

Maintaining Exact Distances under Multiple Edge Failures
Ran Duan and Hanlin Ren
(Tsinghua University, China; University of Oxford, UK)

Publisher's Version Article: stoc22main-p262-p doi:10.1145/3519935.3520002

Session 6C

Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany; RelationalAI, USA)

Publisher's Version Article: stoc22main-p200-p doi:10.1145/3519935.3519990

Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses
Jakub Tětek and Mikkel Thorup
(University of Copenhagen, Denmark)

Publisher's Version Article: stoc22main-p748-p doi:10.1145/3519935.3520059

Low-Rank Approximation with 1/𝜖^1/3 Matrix-Vector Products
Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff
(Carnegie Mellon University, USA; IBM Research, USA)

Publisher's Version Article: stoc22main-p190-p doi:10.1145/3519935.3519988

Sublinear Time Spectral Density Estimation
Vladimir Braverman, Aditya Krishnan, and Christopher Musco
(Johns Hopkins University, USA; New York University, USA)

Publisher's Version Article: stoc22main-p289-p doi:10.1145/3519935.3520009

Memory Bounds for the Experts Problem
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou
(Northwestern University, USA; Carnegie Mellon University, USA)

Publisher's Version Article: stoc22main-p912-p doi:10.1145/3519935.3520069

Session 7A

A Strong Version of Cobham’s Theorem
Philipp Hieronymi and Christian Schulz
(University of Bonn, Germany; University of Illinois at Urbana-Champaign, USA)

Publisher's Version Article: stoc22main-p54-p doi:10.1145/3519935.3519958

3.1n − o(n) Circuit Lower Bounds for Explicit Functions
Jiatu Li and Tianqi Yang
(Tsinghua University, China)

Publisher's Version Article: stoc22main-p151-p doi:10.1145/3519935.3519976

The Approximate Degree of DNF and CNF Formulas
Alexander A. Sherstov
(University of California at Los Angeles, USA)

Publisher's Version Article: stoc22main-p255-p doi:10.1145/3519935.3520000

Verifying the Unseen: Interactive Proofs for Label-Invariant Distribution Properties
Tal Herman and Guy N. Rothblum
(Weizmann Institute of Science, Israel)

Publisher's Version Article: stoc22main-p189-p doi:10.1145/3519935.3519987

Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev
(University of Waterloo, Canada; University of Liverpool, UK)

Publisher's Version Article: stoc22main-p156-p doi:10.1145/3519935.3519978

Session 7B

Robustly Learning Mixtures of k Arbitrary Gaussians
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala
(Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA)

Publisher's Version Article: stoc22main-p29-p doi:10.1145/3519935.3519953

Clustering Mixtures with Almost Optimal Separation in Polynomial Time
Allen Liu and Jerry Li
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)

Publisher's Version Article: stoc22main-p318-p doi:10.1145/3519935.3520012

Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian
(University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA)

Publisher's Version Article: stoc22main-p338-p doi:10.1145/3519935.3520014

List-Decodable Covariance Estimation
Misha Ivkov and Pravesh K. Kothari
(Carnegie Mellon University, USA)

Publisher's Version Article: stoc22main-p276-p doi:10.1145/3519935.3520006

Session 7C

On the Optimal Time/Space Tradeoff for Hash Tables
Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu
(Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore)

Publisher's Version Article: stoc22main-p114-p doi:10.1145/3519935.3519969

An Extendable Data Structure for Incremental Stable Perfect Hashing
Ioana Oriana Bercea and Guy Even
(IT University of Copenhagen, Denmark; Tel Aviv University, Israel)

Publisher's Version Article: stoc22main-p921-p doi:10.1145/3519935.3520070

Almost-Linear ε-Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan
(Dartmouth College, USA; Weizmann Institute of Science, Israel; University of Chicago, USA)

Publisher's Version Article: stoc22main-p237-p doi:10.1145/3519935.3519998

Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari
(Carnegie Mellon University, USA; ETH Zurich, Switzerland; TU Munich, Germany)

Publisher's Version Article: stoc22main-p405-p doi:10.1145/3519935.3520026

Optimal Oblivious Reconfigurable Networks
Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal
(Cornell University, USA; Purdue University, USA)

Publisher's Version Article: stoc22main-p370-p doi:10.1145/3519935.3520020

Session 8A

Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
Noga Ron-Zewi and Ron D. Rothblum
(University of Haifa, Israel; Technion, Israel)

Publisher's Version Article: stoc22main-p38-p doi:10.1145/3519935.3519956

Rate One-Third Non-malleable Codes
Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar
(National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p121-p doi:10.1145/3519935.3519972

Deniable Encryption in a Quantum World
Andrea Coladangelo, Shafi Goldwasser, and Umesh Vazirani
(University of California at Berkeley, USA; Simons Institute for the Theory of Computing Berkeley, USA)

Publisher's Version Article: stoc22main-p365-p doi:10.1145/3519935.3520019

On the Complexity of Two-Party Differential Privacy
Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia
(Tel Aviv University, Israel)

Publisher's Version Article: stoc22main-p167-p doi:10.1145/3519935.3519982

Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Waterloo, Canada)

Publisher's Version Article: stoc22main-p6-p doi:10.1145/3519935.3519947

Session 8B

Entropic Independence: Optimal Mixing of Down-Up Random Walks
Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong
(Stanford University, USA)

Publisher's Version Article: stoc22main-p635-p doi:10.1145/3519935.3520048

Simple Parallel Algorithms for Single-Site Dynamics
Hongyang Liu and Yitong Yin
(Nanjing University, China)

Publisher's Version Article: stoc22main-p240-p doi:10.1145/3519935.3519999

Low-Temperature Ising Dynamics with Random Initializations
Reza Gheissari and Alistair Sinclair
(University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p87-p doi:10.1145/3519935.3519964

Computational Thresholds for the Fixed-Magnetization Ising Model
Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins
(University of Colorado Boulder, USA; University of California at Santa Cruz, USA; University of Illinois at Chicago, USA)

Publisher's Version Article: stoc22main-p265-p doi:10.1145/3519935.3520003

Approximate Counting and Sampling via Local Central Limit Theorems
Vishesh Jain, Will Perkins, Ashwin Sah, and Mehtaab Sawhney
(Stanford University, USA; University of Illinois at Chicago, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p49-p doi:10.1145/3519935.3519957

Session 8C

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany; University of California at Berkeley, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version Article: stoc22main-p825-p doi:10.1145/3519935.3520066

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu
(University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p479-p doi:10.1145/3519935.3520032

Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin and Yinzhan Xu
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p511-p doi:10.1145/3519935.3520036

Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang
(Tsinghua University, China; Tel Aviv University, Israel)

Publisher's Version Article: stoc22main-p682-p doi:10.1145/3519935.3520057

Counting Small Induced Subgraphs with Hereditary Properties
Jacob Focke and Marc Roth
(CISPA, Germany; University of Oxford, UK)

Publisher's Version Article: stoc22main-p287-p doi:10.1145/3519935.3520008

Session 9A

Pseudodeterminism: Promises and Lowerbounds
Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran
(Ben-Gurion University of the Negev, Israel; Iowa State University, USA; University of Nebraska-Lincoln, USA)

Publisher's Version Article: stoc22main-p587-p doi:10.1145/3519935.3520043

Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar
(University of Waterloo, Canada; Georgetown University, USA; University of Warwick, UK; Simon Fraser University, Canada)

Publisher's Version Article: stoc22main-p558-p doi:10.1145/3519935.3520041

Robustness of Average-Case Meta-Complexity via Pseudorandomness
Rahul Ilango, Hanlin Ren, and Rahul Santhanam
(Massachusetts Institute of Technology, USA; Oxford University, UK)

Publisher's Version Article: stoc22main-p644-p doi:10.1145/3519935.3520051

Extractors for Sum of Two Sources
Eshan Chattopadhyay and Jyun-Jie Liao
(Cornell University, USA)

Publisher's Version Article: stoc22main-p86-p doi:10.1145/3519935.3519963

Session 9B

Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
Fabrizio Grandoni, Afrouz Jabal Ameli, and Vera Traub
(USI-SUPSI, Switzerland; ETH Zurich, Switzerland)

Publisher's Version Article: stoc22main-p498-p doi:10.1145/3519935.3520035

An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang
(University of Washington, USA)

Publisher's Version Article: stoc22main-p778-p doi:10.1145/3519935.3520062

Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan
(Google Research, Switzerland; Google Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc22main-p313-p doi:10.1145/3519935.3520011

Explainable k-Means: Don’t Be Greedy, Plant Bigger Trees!
Konstantin Makarychev and Liren Shan
(Northwestern University, USA)

Publisher's Version Article: stoc22main-p681-p doi:10.1145/3519935.3520056

Session 9C

Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary
Adam Karczmarz, Anish Mukherjee, and Piotr Sankowski
(University of Warsaw, Poland; IDEAS NCBR, Poland)

Publisher's Version Article: stoc22main-p700-p doi:10.1145/3519935.3520058

Dynamic Suffix Array with Polylogarithmic Queries and Updates
Dominik Kempa and Tomasz Kociumaka
(Stony Brook University, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc22main-p760-p doi:10.1145/3519935.3520061

Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer
(Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA)

Publisher's Version Article: stoc22main-p795-p doi:10.1145/3519935.3520064

On the Complexity of Dynamic Submodular Maximization
Xi Chen and Binghui Peng
(Columbia University, USA)

Publisher's Version Article: stoc22main-p20-p doi:10.1145/3519935.3519951

proc time: 0.31