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