Accepted Papers
-
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)