STOC 2022 Accepted Papers

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

Towards Optimal Lower Bounds for kmedian and kmeans Coresets
Vincent CohenAddad (Google Research, Switzerland), Kasper Green Larsen (Aarhus University), David Saulpic (Sorbonne Université) and Chris Schwiegelshohn (Aarhus University)

Efficient Mean Estimation with Pure Differential Privacy via a SumofSquares Exponential Mechanism
Sam Hopkins (UC Berkeley), Gautam Kamath (University of Waterloo) and Mahbod Majid (University of Waterloo)

Breaking the n^{k} Barrier for Minimum kcut on Simple Graphs
Zhiyang He (MIT) and Jason Li (UC Berkeley)

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

Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games
Constantinos Daskalakis (EECS, MIT) and Noah Golowich (Google Research)

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

PublicKey Quantum Money with a Classical Bank
Omri Shmueli (Tel Aviv University)

Robustly Learning Mixtures of k Arbitrary Gaussians
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)

Matrix Discrepancy from Quantum Communication
Sam Hopkins (UC Berkeley), Prasad Raghavendra (U.C. Berkeley) and Abhishek Shetty (UC Berkeley)

Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
Venkatesan Guruswami (Carnegie Mellon University), Pravesh K. Kothari (Carnegie Mellon University) and Peter Manohar (Carnegie Mellon University)

Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
Noga RonZewi (University of Haifa) and Ron Rothblum (Technion)

Approximate counting and sampling via local central limit theorems
Vishesh Jain (Stanford University), Will Perkins (UIC), Ashwin Sah (MIT) and Mehtaab Sawhney (MIT)

A strong version of Cobham's theorem
Philipp Hieronymi (Universität Bonn) and Christian Schulz (University of Illinois)

A PTAS for Unsplittable Flow on a Path
Fabrizio Grandoni (IDSIA, USISUPSI), Tobias Mömke (University of Augsburg) and Andreas Wiese (Vrije Universiteit Amsterdam)

Optimizing strongly interacting fermionic Hamiltonians
Matthew B. Hastings (Microsoft Research) and Ryan O'Donnell (Carnegie Mellon University)

Uniform Approximations for Randomized Hadamard Transforms with Applications
Yeshwanth Cherapanamjeri (UC Berkeley) and Jelani Nelson (UC Berkeley)

An area law for 2D frustrationfree spin systems
Anurag Anshu (University of California, Berkeley), Itai Arad (Technion) and David Gosset (University of Waterloo)

Extractors for Sum of Two Sources
Eshan Chattopadhyay (Cornell University) and JyunJie Liao (Cornell University)

Lowtemperature Ising dynamics with random initializations
Reza Gheissari (U.C. Berkeley) and Alistair Sinclair (U.C. Berkeley)

Positive spectrahedra: Invariance principles and Pseudorandom generators
Srinivasan Arunachalam (IBM T. J. Watson Research Center) and Penghui Yao (Nanjing University)

Approximate Polymorphisms
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)

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

Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
Vishwas Bhargava (Rutgers University), Sumanta Ghosh (IIT Bombay), Mrinal Kumar (IIT Bombay) and Chandra Kanta Mohapatra (IIT Bombay)

On the Optimal Time/Space Tradeoff for Hash Tables
Michael Bender (Stony Brook University), Martin FarachColton (Rutgers University), John Kuszmaul (Yale University), William Kuszmaul (MIT) and Mingmou Liu (Nanyang Technological University)

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

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

Rate OneThird Nonmalleable Codes
Divesh Aggarwal (National University of Singapore) ⓡ Sruthi Sekar (UC Berkeley, California) ⓡ Bhavana Kanukurthi (Indian Institute of Science Bangalore) ⓡ Maciej Obremski (National University of Singapore) ⓡ Sai Lakshmi Bhavana Obbattu (Microsoft Research, Bangalore)

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

Distributed quantum inner product estimation
Anurag Anshu (UC Berkeley), Zeph Landau (UC Berkeley) and Yunchao Liu (UC Berkeley)

Binary perceptron: efficient algorithms can find solutions in a rare wellconnected cluster
Emmanuel Abbe (EPFL), Shuangping Li (Princeton University) and Allan Sly (Princeton University)

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

Deterministic, NearLinear εApproximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal (Duke University), HsienChih Chang (Department of Computer Science, Dartmouth College), Sharath Raghvendra (Virginia Tech) and Allen Xiao (Duke University)

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

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

Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to > 1/2 Adversarial Corruption
Meghal Gupta (Microsoft Research), Yael Tauman Kalai (Microsoft Research) and Rachel Yun Zhang (MIT)

Learning lowdegree functions from a logarithmic number of random queries
Alexandros Eskenazis (University of Cambridge) and Paata Ivanisvili (University of California, Irvine)

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

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

A Subpolynomial Approximation Algorithm for Graph Crossing Number in LowDegree Graphs
Julia Chuzhoy (Toyota Technological Institute at Chicago) and Zihan Tan (University of Chicago)

The Optimal Error Resilience of Interactive Communication Over Binary Channels
Rachel Yun Zhang (MIT) and Meghal Gupta (Microsoft Research)

Online Edge Coloring via Tree Recurrences and Correlation Decay
Janardhan Kulkarni (Microsoft), Yang P. Liu (Stanford University), Mehtaab Sawhney (MIT), Ashwin Sah (MIT) and Jakub Tarnawski (Microsoft)

Verifying The Unseen: Interactive Proofs for LabelInvariant Distribution Properties
Tal Herman (Weizmann Institute of Science) and Guy Rothblum (Weizmann Institute of Science)

LowRank Approximation with 1/ε^{1/3} MatrixVector Products
Ainesh Bakshi (Carnegie Mellon University), Ken Clarkson (IBM Research) and David P. Woodruff (Carnegie Mellon University)

Testing thresholds for highdimensional sparse random geometric graphs
Siqi Liu (UC Berkeley), Sidhanth Mohanty (UC Berkeley), Tselil Schramm (Stanford) and Elizabeth Yang (UC Berkeley)

AlmostOptimal SublinearTime Edit Distance in the Low Distance Regime
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)

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

Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs are not Unique Neighbor Expanders
Amitay Kamber (University of Cambridge) and Tali Kaufman (Bar Ilan University)

The Query Complexity of Certification
Guy Blanc (Stanford University), Caleb Koch (Stanford University), Jane Lange (MIT) and LiYang Tan (Stanford University)

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

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

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

No selfconcordant barrier interior point method is strongly polynomial
Xavier Allamigeon (INRIA & Ecole Polytechnique), Stéphane Gaubert (INRIA & Ecole Polytechnique) and Nicolas Vandame (INRIA & Ecole Polytechnique)

AlmostLinear εEmulators for Planar Graphs
HsienChih Chang (Dartmouth College), Robert Krauthgamer (Weizmann Institute of Science) and Zihan Tan (The University of Chicago)

Simple Parallel Algorithms for SingleSite Dynamics
Hongyang Liu (Nanjing University) and Yitong Yin (Nanjing University)

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

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

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

Computational thresholds for the fixedmagnetization Ising model
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)

Hypercontractivity on High Dimensional Expanders
Tom Gur (University of Warwick), Noam Lifshitz (Hebrew University of Jerusalem) and Siqi Liu (UC Berkeley)

Brooks’ Theorem in Graph Streams: A SinglePass SemiStreaming Algorithm for ∆Coloring
Sepehr Assadi (Rutgers University), Pankaj Kumar (Charles University) and Parth Mittal (Rutgers University)

ListDecodable Covariance Estimation
Misha Ivkov (CMU) and Pravesh K. Kothari (CMU)

Circuits Resilient to ShortCircuit Errors
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)

Counting Small Induced Subgraphs with Hereditary Properties
Jacob Focke (CISPA Helmholtz Center for Information Security) and Marc Roth (University of Oxford)

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

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

Improved Approximations for Euclidean kmeans and kmedian, via Nested QuasiIndependent Sets
Vincent CohenAddad (Google), Hossein Esfandiari (Google), Vahab Mirrokni (Google Research) and Shyam Narayanan (Massachusetts Institute of Technology)

Clustering Mixtures with Almost Optimal Separation in Polynomial Time
Allen Liu (MIT) and Jerry Li (Microsoft Research)

On the Hardness of Dominant Strategy Mechanism Design
Shahar Dobzinski (Weizmann Institute of Science), Shiri Ron (Weizmann Institute of Science) and Jan Vondrak (Stanford)

Clustering Mixture Models in AlmostLinear Time via ListDecodable Mean Estimation
Ilias Diakonikolas (UW Madison), Daniel Kane (UCSD), Daniel Kongsgaard (University of California, San Diego), Jerry Li (Microsoft Research) and Kevin Tian (Stanford University)

Byzantine Agreement in Polynomial Time with NearOptimal Resilience
ShangEn Huang (University of Michigan), Seth Pettie (University of Michigan) and Leqi Zhu (University of Michigan)

Deterministic Graph Coloring in the Streaming Model
Sepehr Assadi (Rutgers University), Andrew Chen (Cornell University) and Glenn Sun (UCLA)

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

Directed flowaugmentation
Eun Jung Kim (Université ParisDauphine, PSL Research University, CNRS), Stefan Kratsch (HumboldtUniversität zu Berlin), Marcin Pilipczuk (University of Warsaw) and Magnus Wahlström (Royal Holloway, University of London)

Deniable Encryption in a Quantum World
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)

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

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

Expanders via Local Edge Flips in Quasilinear Time
George Giakkoupis (Inria, Rennes, France)

NearOptimal Distributed Degree+1 Coloring
Magnus M. Halldorsson (Reykjavik University), Fabian Kuhn (University of Freiburg), Alexandre Nolin (Reykjavik University) and Tigran Tonoyan (Technion)

Locally Testable Codes with constant rate, distance, and locality
Irit Dinur (Weizmann), Shai Evra (Hebrew U), Ron Livne (Hebrew U), Alexander Lubotzky (Weizmann) and Shahar Mozes (Hebrew U)

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

HopConstrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
Bernhard Haeupler (Carnegie Mellon University & ETH Zurich) ⓡ Harald Räcke (Technical University Munich) ⓡ Mohsen Ghaffari (ETH Zurich)

Distributed ΔColoring Plays HideandSeek
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)

On Inapproximability of Satisfiable 3CSPs
Amey Bhangale (University of California, Riverside), Subhash Khot (New York University) and Dor Minzer (Massachusetts Institute of Technology)

Computing Simple Mechanisms: LiftandRound over Marginal Reduced Forms
Yang Cai (Yale University), Argyris Oikonomou (Yale University) and Mingfei Zhao (Google Research)

The Shortest Even Cycle Problem is Tractable
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)

NearOptimal NoRegret Learning for Correlated Equilibria in MultiPlayer GeneralSum Games
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)

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
Timothy M. Chan (UIUC), Virginia Vassilevska Williams (Massachusetts Institute of Technology) and Yinzhan Xu (Massachusetts Institute of Technology)

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

Breaching the 2Approximation Barrier for the Forest Augmentation Problem
Fabrizio Grandoni (IDSIA, USISUPSI), Afrouz Jabal Ameli (IDSIA, USISUPSI) and Vera Traub (ETH Zurich)

Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin (MIT) and Yinzhan Xu (MIT)

Twinwidth IV: ordered graphs and matrices
É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)

Edge Connectivity Augmentation in NearLinear Time
Ruoxu Cen (Duke University), Jason Li (UC Berkeley) and Debmalya Panigrahi (Duke University)

Deterministic (1+ε)Approximate Maximum Matching with poly(1 /ε) Passes in the SemiStreaming Model and Beyond
Manuela Fischer (ETH Zurich), Slobodan Mitrović (UC Davis) and Jara Uitto (Aalto University)

Hypercontractivity on High Dimensional Expanders
Mitali Bafna (Harvard), Max Hopkins (UCSD), Tali Kaufman (Bar Ilan University) and Shachar Lovett (UCSD)

WorstCase to AverageCase Reductions via Additive Combinatorics
Vahid R. Asadi (University of Waterloo), Alexander Golovnev (Georgetown University), Tom Gur (University of Warwick) and Igor Shinkar (Simon Fraser University)

LocalitySensitive Orderings and Applications to Reliable Spanners
Arnold Filtser (BarIlan University) and Hung Le (University of Massachusetts Amherst)

Pseudodeterminism: Promises and Lowerbounds
Peter Dixon (Iowa State University), A. Pavan (Iowa State University), Jason Vander Woude (University of NebraskaLincoln) and N. V. Vinodchandran (University of NebraskaLincoln)

Setmultilinear and noncommutative formula lower bounds for iterated
matrix multiplication
Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA), Nutan Limaye (ITUCopenhagen) and Srikanth Srinivasan (Aarhus University)

NearOptimal Quantum Algorithms for Multivariate Mean Estimation
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
Zhiyi Huang (The University of Hong Kong), Xinkai Shu (The University of Hong Kong) and Shuyi Yan (Tsinghua University)

Nearly Optimal Vertex FaultTolerant Spanners in Optimal Time: Sequential, Distributed and Parallel
Merav Parter (Weizmann IS)

Entropic Independence: Optimal Mixing of DownUp Random Walks
Nima Anari (Stanford University), Vishesh Jain (Stanford University), Frederic Koehler (UC Berkeley), Huy Tuan Pham (Stanford University) and ThuyDuong Vuong (Stanford University)

Bypassing the Surface Embedding: Approximation Schemes for Network Design in MinorFree Graphs
Vincent CohenAddad (Google Research, Switzerland)

Kalman Filtering with Adversarial Corruptions
Sitan Chen (UC Berkeley), Frederic Koehler (UC Berkeley), Ankur Moitra (Math & CSAIL, MIT) and Morris Yau (MIT)

Robustness of AverageCase MetaComplexity via Pseudorandomness
Rahul Ilango (MIT), Hanlin Ren (Oxford University) and Rahul Santhanam (Oxford University)

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

Sparsified Block Elimination for Directed Laplacians
Richard Peng (Georgia Tech) and Zhuoqing Song (Fudan University)

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

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

Explainable kmeans. Don’t be greedy, plant bigger trees!
Konstantin Makarychev (Northwestern University) and Liren Shan (Northwestern University)

Faster MinPlus Product for Monotone Instances
Shucheng Chi (Tsinghua University), Ran Duan (Tsinghua University), Tianle Xie (Tsinghua University) and Tianyi Zhang (Tel Aviv University)

Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
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)

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

Matrix anticoncentration inequalities with applications
Zipei Nie (Lagrange Mathematics and Computing Research Center)

Dynamic Suffix Array with Polylogarithmic Queries and Updates
Dominik Kempa (Stony Brook University) and Tomasz Kociumaka (UC Berkeley)

An Improved Approximation Algorithm for the Minimum kEdge Connected MultiSubgraph Problem
Anna Karlin (University of Washington), Nathan Klein (University of Washington), Shayan Oveis Gharan (University of Washington) and Xinzhi Zhang (University of Washington)

On the Complexity of CSPbased Ideal Membership Problems
Andrei A. Bulatov (Simon Fraser University) and Akbar Rafiey (Simon Fraser University)

Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
Amos Beimel (BenGurion 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)

Pricing Ordered Items
Shuchi Chawla (UT Austin), Rojin Rezvan (UT Austin), Yifeng Teng (Google Research) and Christos Tzamos (University of WisconsinMadison)

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
Amir Abboud (Weizmann Institute of Science), Karl Bringmann (Saarland University), Seri Khoury (UC Berkeley) and Or Zamir (Institute for Advanced Study)

Hamiltonian Complexity in the Thermodynamic Limit
Dorit Aharonov (Hebrew University) and Sandy Irani (UC Irvine)

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
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)

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

An extendable data structure for incremental stable perfect hashing
Ioana Bercea (IT University of Copenhagen) and Guy Even (TelAviv University)

Parallel Repetition For All 3Player Games Over Binary Alphabet
Uma Girish (Princeton University), Justin Holmgren (NTT Research), Kunal Mittal (Princeton University), Ran Raz (Princeton University) and Wei Zhan (Princeton University)

A Characterization of Approximability for Biased CSPs
Euiwoong Lee (University of Michigan) and Suprovat Ghoshal (Indian Institute of Science, Bangalore)

Quantum Garbled Circuits
Zvika Brakerski (Weizmann Institute) and Henry Yuen (Columbia University)

Undirected (1+epsilon)Shortest Paths via MinorAggregates: NearOptimal Deterministic Parallel & Distributed Algorithms
Václav Rozhoň (ETH Zurich) ⓡ Christoph Grunau (ETH Zurich) ⓡ Bernhard Haeupler (ETH Zurich & Carnegie Mellon University) ⓡ Goran Zuzic (ETH Zurich) ⓡ Jason Li (UC Berkeley)

Complexity classification of counting graph homomorphisms modulo a prime number
Andrei Bulatov (Simon Fraser University) and Amirhossein Kazeminia (Simon Fraser University)

Fixedparameter tractability of Graph Isomorphism in graphs with an excluded minor
Daniel Lokshtanov (University of California Santa Barbara, USA), Michał Pilipczuk (University of Warsaw), Marcin Pilipczuk (University of Warsaw) and Saket Saurabh (IMSc)

Flow Time Scheduling and Prefix BeckFiala
Nikhil Bansal (University of Michigan), Lars Rohwedder (EPFL) and Ola Svensson (EPFL)

Improved Communication Complexity of FaultTolerant Consensus
Jan Olkowski (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland) and Dariusz R. Kowalski (Augusta University, Augusta, Georgia)

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