Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Authors: Shiri Chechik (Tel-Aviv University); Tianyi Zhang (Tsinghua University)

Adversarial Bandits with Knapsacks
Authors: Nicole Immorlica (Microsoft Research New York); Karthik Abinav Sankararaman (University of Maryland College Park); Robert Schapire, Aleksandrs Slivkins (Microsoft Research New York)

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Authors: Makrand Sinha (CWI); Ronald de Wolf (QuSoft, CWI and University of Amsterdam)

Modified log-Sobolev inequalities for strongly log-concave distributions
Authors: Mary Cryan, Heng Guo, Giorgos Mousa (University of Edinburgh)

Lower bounds for maximal matchings and maximal independent sets
Authors: Alkida Balliu (Aalto University); Sebastian Brandt (ETH Zurich); Juho Hirvonen, Dennis Olivetti (Aalto University); Mikaël Rabie (Aalto University and University Paris Sorbonne); Jukka Suomela (Aalto University)

Quantum Log-Approximate-Rank Conjecture is also False
Authors: Anurag Anshu (University of Waterloo, Perimeter Institute); Naresh Goud Boddu (National University of Singapore); Dave Touchette (University of Waterloo, Perimeter Institute, Universite de Sherbrooke)

Noise Sensitivity on the p-Biased Hypercube
Authors: Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer (Institute for Advanced Study)

General Framework for Metric Optimization Problems with Delay or with Deadlines
Authors: Yossi Azar, Noam Touitou (Tel Aviv university)

(Nearly) Sample Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Authors: Vasileios Nakos, Zhao Song, Zhengyu Wang (Harvard University)

Expander Graphs – Both local and global
Authors: Michael Chapman, Nati Linial (Hebrew University of Jerusalem); Yuval Peled (Courant institute, NYU)

Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
Authors: Chao Tao, Qin Zhang (Indiana University); Yuan Zhou (Indiana University and UIUC)

Balancing Straight-Line Programs
Authors: Moses Ganardi (Universität Siegen); Artur Jez (University of Wroclaw); Markus Lohrey (Universität Siegen)

More barriers for rank methods, via a “numeric to symbolic” transfer
Authors: Ankit Garg (Microsoft Research India, Bangalore); Visu Makam (Institute for Advanced Study); Rafael Oliveira (University of Toronto and Simons Institute for the Theory of Computing); Avi Wigderson (Institute for Advanced Study)

Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
Authors: David G. Harris (University of Maryland)

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
Authors: Lijie Chen (MIT)

The complexity of 3-colouring H-colourable graphs
Authors: Andrei Krokhin, Jakub Opršal (Durham University)

Polynomial calculus space and resolution width
Authors: Nicola Galesi (Sapienza University Rome); Leszek A. Kolodziejczyk (University of Warsaw); Neil Thapen (Czech Academy of Sciences)

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Authors: Jan van den Brand, Danupon Nanongkai (KTH Royal Institute of Technology)

Reed-Muller codes polarize
Authors: Emmanuel Abbe (EPFL and Princeton University); Min Ye (Princeton University)

Finding monotone patterns in sublinear time
Authors: Omri Ben-Eliezer (Tel-Aviv University); Clement L. Canonne (Stanford University); Shoham Letzter (ETH-ITS, ETH Zurich); Erik Waingarten (Columbia University)

Exponentially Faster Massively Parallel Maximal Matching
Authors: Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris (University of Maryland)

Beyond the Lovasz Local Lemma: Point to Set Correlations and Their Algorithmic Applications
Authors: Dimitris Achlioptas (University of California Santa Cruz); Fotis Iliopoulos, Alistair Sinclair (University of California Berkeley)

Random $k$-out subgraph leaves only $O(n/k)$ inter-component edges
Authors: Jacob Holm (University of Copenhagen); Valerie King (University of Victoria); Mikkel Thorup (University of Copenhagen); Or Zamir, Uri Zwick (Tel Aviv University)

Stoquastic PCP vs. Randomness
Authors: Dorit Aharonov (Hebrew University of Jerusalem); Alex B. Grilo (CWI and QuSoft)

Quantum advantage with noisy shallow circuits in 3D
Authors: Sergey Bravyi (IBM T.J. Watson Research Center); David Gosset (University of Waterloo); Robert Koenig (Technical University of Munich); Marco Tomamichel (University of Technology Sydney)

Polylogarithmic Guarantees for Generalized Reordering Buffer Management
Authors: Matthias Englert (University of Warwick); Harald Räcke, Richard Stotz (Technical University of Munich)

Sensitive Distance and Reachability Oracles for Large Batch Updates
Authors: Jan van den Brand (KTH Royal Institute of Technology); Thatchaphol Saranurak (Toyota Technological Institute at Chicago)

Agreement testing theorems on layered set systems
Authors: Yotam Dikstein, Irit Dinur (Weizmann Institute of Science)

Waring Rank, Parameterized and Exact Algorithms
Authors: Kevin Pratt (Computer Science Department, Carnegie Mellon University)

Beyond trace reconstruction: Population recovery from the deletion channel
Authors: Frank Ban (UC Berkeley); Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha (Columbia University)

Near-Optimal Massively Parallel Graph Connectivity
Authors: Soheil Behnezhad (University of Maryland); Laxman Dhulipala (Carnegie Mellon University); Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni (Google Research)

Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers
Authors: Tomer Ezra, Michal Feldman (Tel Aviv University); Eric Neyman (Columbia University); Inbal Talgam-Cohen (Technion); S. Matthew Weinberg (Princeton University)

A Quantum Query Complexity Trichotomy for Regular Languages
Authors: Scott Aaronson (UT Austin); Daniel Grier, Luke Schaeffer (MIT)

A Deterministic Algorithm for Counting Colorings with 2Δ Colors
Authors: Jingcheng Liu, Alistair Sinclair (UC Berkeley); Piyush Srivastava (TIFR)

Approximation Schemes for a Buyer with Independent Items via Symmetries
Authors: Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg (Princeton University)

The Role of Interactivity in Local Differential Privacy
Authors: Matthew Joseph, Jieming Mao, Seth Neel, Aaron Roth (University of Pennsylvania)

An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices
Authors: Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek (Harvard University); Shravas Rao (New York University)

How to Use Heuristics for Differential Privacy
Authors: Seth Neel, Aaron Roth (University of Pennsylvania); Zhiwei Steven Wu (University of Minnesota)

Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces
Authors: Luke Postle (University of Waterloo)

Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Authors: Sepehr Assadi (Princeton University); Sahil Singla (Princeton University and Institute for Advanced Study)

Optimization of the Sherrington-Kirkpatrick Hamiltonian
Authors: Andrea Montanari (Stanford University)

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Authors: Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi (University of Maryland); Cliff Stein (Columbia University); Madhu Sudan (Harvard University)

An Optimal Document Exchange Protocol
Authors: Bernhard Haeupler (CMU)

Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
Authors: Benny Applebaum, Eliran Kachlon (Tel Aviv University)

NEEXP ⊆ MIP*
Authors: Anand Natarajan (California Institute of Technology); John Wright (Massachusetts Institute of Technology)

Fast uniform generation of random graphs with given degree sequences
Authors: Andrii Arman (Monash University); Pu Gao (University of Waterloo); Nick Wormald (Monash University)

Parallel Reachability in Almost Linear Work and Square Root Depth
Authors: Yang Liu, Aaron Sidford, Arun Jambulapati (Stanford University)

Multi-Resolution Hashing for Fast Pairwise Summations
Authors: Moses Charikar, Paris Siminelakis (Stanford University)

Automating Resolution is NP-Hard
Authors: Albert Atserias, Moritz Müller (Universitat Politecnica de Catalunya)

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
Authors: Jan van den Brand, Danupon Nanongkai (KTH Royal Institute of Technology); Thatchaphol Saranurak (Toyota Technological Institute at Chicago)

Faster Matroid Intersection
Authors: Deeparnab Chakrabarty (Dartmouth College); Yin Tat Lee (University of Washington); Aaron Sidford (Stanford University); Sahil Singla (Princeton University and Institute for Advanced Study); Sam Chiu-wai Wong (Microsoft Research)

Quasilinear time list-decodable codes for space bounded channels
Authors: Swastik Kopparty (Rutgers University and IAS); Ronen Shaltiel (University of Haifa); Jad Silbak (Tel-Aviv University)

Why are Proof Complexity Lower Bounds Hard?
Authors: Jan Pich, Rahul Santhanam (University of Oxford)

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
Authors: Vincent Cohen-Addad (CNRS & Sorbonne Université); Marcin Pilipczuk, Michał Pilipczuk (Institute of Informatics, University of Warsaw, Poland)

Junta-correlation is testable
Authors: Anindya De (UPenn); Elchanan Mossel (MIT); Joe Neeman (UT Austin)

Planar Graphs have Bounded Queue-Number
Authors: Vida Dujmović (University of Ottawa); Gwenaël Joret (Université Libre de Bruxelles); Piotr Micek (Jagiellonian University); Pat Morin (Carleton University); Torsten Ueckerdt (Karlsruhe Institute of Technology); David R. Wood (Monash University)

Breaking of 1RSB in random MAX-NAE-SAT
Authors: Zsolt Bartha (University of California at Berkeley); Nike Sun (Massachusetts Institute of Technology); Yumeng Zhang (Stanford University)

Efficient Construction of Rigid Matrices Using an NP Oracle
Authors: Josh Alman, Lijie Chen (MIT)

Derandomization from Algebraic Hardness: Treading the Borders
Authors: Zeyu Guo, (Indian Institute of Technology, Kanpur); Mrinal Kumar (University of Toronto and Indian Institute of Technology, Bombay); Ramprasad Saptharishi (Tata Institute of Fundamental Research); Noam Solomon (Massachusetts Institute of Technology)

Non-Malleable Commitments using Goldreich-Levin List Decoding
Authors: Vipul Goyal (Carnegie Mellon University); Silas Richelson (UC Riverside)

Tight Bounds for Online Edge Coloring
Authors: Ilan Reuven Cohen (CWI); Binghui Peng (Tsinghua University); David Wajc (CMU)

Smoothed Analysis in Unsupervised Learning via Decoupling
Authors: Aditya Bhaskara (School of Computing, University of Utah); Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan (Northwestern University)

The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
Authors: Enric Boix-Adserà, Matthew Brennan, Guy Bresler (MIT)

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
Authors: Mohsen Ghaffari (ETH Zurich, Switzerland); Fabian Kuhn (University of Freiburg, Germany); Jara Uitto (ETH Zurich, Switzerland and University of Freiburg, Germany)

A New Deterministic Algorithm for Dynamic Set Cover
Authors: Sayan Bhattacharya (University of Warwick); Monika Henzinger (University of Vienna); Danupon Nanongkai (KTH Royal Institute of Technology)

Fast generalized DFTs for all finite groups
Authors: Chris Umans (Caltech)

Radio Network Coding Requires Logarithmic Overhead
Authors: Klim Efremenko (Ben-Gurion University); Gillat Kol, Raghuvansh R. Saxena (Princeton University)

A Tight Analysis of Bethe Approximation for Permanent
Authors: Nima Anari (Stanford University); Alireza Rezaei (University of Washington)

Online Matching with General Arrivals
Authors: Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson (EPFL); David Wajc (CMU)

New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Authors: Nikhil Bansal (CWI and TU Eindhoven); Ola Svensson (EPFL); Luca Trevisan (UC Berkeley)

Near-Linear-Time Approximation Schemes for Clustering in Doubling Metrics
Authors: Vincent Cohen-Addad (Sorbonne Université, UPMC Univ Paris 06, CNRS, LIP6, Paris, France); Andreas Emil Feldmann (Charles University in Prague, Czechia); David Saulpic (École Normale Supérieure, Paris)

Spectral analysis of matrix scaling and operator scaling
Authors: Tsz Chiu Kwok (Shanghai University of Finance and Economics); Lap Chi Lau, Akshay Ramachandran (University of Waterloo)

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Authors: Vedat Levi Alev (University of Waterloo); Fernando Granha Jeronimo (University of Chicago); Madhur Tulsiani (TTI-Chicago)

Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Authors: Aviad Rubinstein (Stanford University); Saeed Seddighin (University of Maryland); Zhao Song (Simons at Berkeley); Xiaorui Sun (University of Illinois at Chicago)

Hardness Magnification for all Sparse NP Languages
Authors: Lijie Chen (MIT); Ce Jin (Tsinghua University); Ryan Williams (MIT)

A characterization of graph properties testable for general planar graphs with one-sided error (It’s all about forbidden subgraphs)
Authors: Artur Czumaj (University of Warwick); Christian Sohler (TU Dortmund)

Parametric Shortest Paths in Planar Graphs
Authors: Kshitij Gajjar, Jaikumar Radhakrishnan (Tata Institute of Fundamental Research)

Laconic Conditional Disclosure of Secrets and Applications
Authors: Nico Döttling (CISPA Helmholtz Center for Information Security); Sanjam Garg (University of California, Berkeley); Vipul Goyal, Giulio Malavolta (Carnegie Mellon University)

SETH-hardness of Coding Problems
Authors: Noah Stephens-Davidowitz, Vinod Vaikuntanathan (Massachusetts Institute of Technology)

Leakage-Resilient Secret Sharing Against Colluding Parties
Authors: Ashutosh Kumar, Raghu Meka, Amit Sahai (UCLA)

Perfect zero knowledge for quantum multiprover interactive proofs
Authors: Alex B. Grilo (CWI and QuSoft); William Slofstra (IQC and Department of Pure Mathematics, University of Waterloo); Henry Yuen (University of Toronto)

Computationally-secure and composable remote state preparation
Authors: Alexandru Gheorghiu, Thomas Vidick (California Institute of Technology)

Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes
Authors: Peter Bürgisser (Technische Universität Berlin); Cole Franks (Rutgers University); Ankig Garg (Microsoft Research India); Rafael Oliveira (University of Toronto); Michael Walter (Korteweg-de Vries Institute for Mathematics, Institute for Theoretical Physics, QuSoft, University of Amsterdam); Avi Wigderson (Institute for Advanced Study)

Inapproximability of Clustering in l_p-metrics
Authors: Vincent Cohen-Addad (CNRS & Sorbonne Université); Karthik C. S. (Weizmann Institute of Science)

Faster polytope rounding, sampling, and volume computation via a sublinear “Ball Walk”
Authors: Oren Mangoubi (Worcester Polytechnic Institute); Nisheeth K. Vishnoi (Yale University)

Sublinear Algorithms for Gap Edit Distance
Authors: Elazar Goldenberg (The Academic College of Tel Aviv-Yaffo); Robert Krauthgamer (Weizmann Institute of Science); Barna Saha (University of California Berkeley)

Learning from Outcomes: Evidence-Consistent Rankings
Authors: Cynthia Dwork (Harvard University); Michael P. Kim, Omer Reingold (Stanford University); Guy N. Rothblum, Gal Yona (Weizmann Institute of Science)

The Kikuchi Hierarchy and Tensor PCA
Authors: Alexander S. Wein (Courant Institute, NYU); Ahmed El Alaoui (Stanford); Cristopher Moore (Santa Fe Institute)

Truly Optimal Euclidean Spanners
Authors: Hung Le (University of Victoria); Shay Solomon (Tel Aviv University)

Efficient Truncated Statistics with Unknown Truncation
Authors: Vasilis Kontonis, Christos Tzamos (UW Madison); Manolis Zampetakis (MIT)

Faster Minimum k-cut of a Simple Graph
Authors: Jason Li (Carnegie Mellon University)

Residual Based Sampling for Online Low Rank Approximation
Authors: Aditya Bhaskara (University of Utah); Silvio Lattanzi (Google Research, Zurich); Sergei Vassilvitskii (Google Research, New York); Morteza Zadimoghaddam (Google Research, Zurich)