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