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 k-median and k-means Coresets
  Vincent Cohen-Addad (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 Sum-of-Squares Exponential Mechanism
  Sam Hopkins (UC Berkeley), Gautam Kamath (University of Waterloo) and Mahbod Majid (University of Waterloo)


• Breaking the n^k Barrier for Minimum k-cut 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)


• Public-Key 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 Ron-Zewi (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, USI-SUPSI), 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 frustration-free 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 Jyun-Jie Liao (Cornell University)


• Low-temperature 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 Farach-Colton (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 Wisconsin-Madison) and Nikos Zarifis (UW Madison)


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


• Rate One-Third Non-malleable 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 well-connected 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, Near-Linear ε-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)


• 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 low-degree functions from a logarithmic number of random queries
  Alexandros Eskenazis (University of Cambridge) and Paata Ivanisvili (University of California, Irvine)


• On the Complexity of Two-Party 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
  Chi-Ning 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 Low-Degree 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 Label-Invariant Distribution Properties
  Tal Herman (Weizmann Institute of Science) and Guy Rothblum (Weizmann Institute of Science)


• Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products
  Ainesh Bakshi (Carnegie Mellon University), Ken Clarkson (IBM Research) and David P. Woodruff (Carnegie Mellon University)


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


• Almost-Optimal Sublinear-Time 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 Li-Yang Tan (Stanford University)


• (Fractional) Online Stochastic Matching via Fine-Grained 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 FPT-Approximation of Branchwidth
  Fedor V. Fomin (University of Bergen) and Tuukka Korhonen (University of Bergen)


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


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


• Simple Parallel Algorithms for Single-Site 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 fixed-magnetization 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 Single-Pass Semi-Streaming Algorithm for ∆-Coloring
  Sepehr Assadi (Rutgers University), Pankaj Kumar (Charles University) and Parth Mittal (Rutgers University)


• List-Decodable Covariance Estimation
  Misha Ivkov (CMU) and Pravesh K. Kothari (CMU)


• Circuits Resilient to Short-Circuit 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 Black-Box 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 k-means and k-median, via Nested Quasi-Independent Sets
  Vincent Cohen-Addad (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 Almost-Linear Time via List-Decodable 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 Near-Optimal Resilience
  Shang-En 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 flow-augmentation
  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)


• 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 Constant-Factor 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)


• Near-Optimal 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 Urbana-Champaign) and Michael A. Forbes (University of Illinois at Urbana-Champaign)


• Hop-Constrained 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 Hide-and-Seek
  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 3-CSPs
  Amey Bhangale (University of California, Riverside), Subhash Khot (New York University) and Dor Minzer (Massachusetts Institute of Technology)


• Computing Simple Mechanisms: Lift-and-Round 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)


• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum 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 Sub-Logarithmic Size Alphabet
  Inbar Ben Yaacov (Tel Aviv University), Gil Cohen (Tel Aviv University) and Tal Yankovitz (Tel Aviv University)


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


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


• Twin-width 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 Near-Linear 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 Semi-Streaming 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)


• Worst-Case to Average-Case 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)


• Locality-Sensitive Orderings and Applications to Reliable Spanners
  Arnold Filtser (Bar-Ilan 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 Nebraska-Lincoln) and N. V. Vinodchandran (University of Nebraska-Lincoln)


• Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
  Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA), Nutan Limaye (ITU-Copenhagen) and Srikanth Srinivasan (Aarhus University)


• Near-Optimal 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 Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed and Parallel
  Merav Parter (Weizmann IS)


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


• Bypassing the Surface Embedding: Approximation Schemes for Network Design in Minor-Free Graphs
  Vincent Cohen-Addad (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 Average-Case Meta-Complexity 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 k-means. Don’t be greedy, plant bigger trees!
  Konstantin Makarychev (Northwestern University) and Liren Shan (Northwestern University)


• Faster Min-Plus 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 anti-concentration 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 k-Edge Connected Multi-Subgraph 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 CSP-based 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 (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)


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


• 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 (Tel-Aviv University)


• Parallel Repetition For All 3-Player 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 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) ⓡ 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)


• Fixed-parameter 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 Beck-Fiala
  Nikhil Bansal (University of Michigan), Lars Rohwedder (EPFL) and Ola Svensson (EPFL)


• 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)


• 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)