Accepted papers
-
MDS matrices over small fields: a proof of the GM-MDS conjecture
Authors: Shachar Lovett (UC San Diego) -
Improved Online Algorithm for Weighted Flow Time
Authors: Yossi Azar, Noam Touitou (Tel Aviv University) -
Bloom Filters, Adaptivity, and the Dictionary Problem
Authors: Michael A. Bender (Stony Brook University); Martin Farach-Colton (Rutgers University); Mayank Goswami (Queens College, CUNY); Rob Johnson (VMware Research); Samuel McCauley (BARC and IT U. Copenhagen); Shikha Singh (Stony Brook University) -
The complexity of general-valued CSPs seen from the other side
Authors: Clement Carbonnel, Miguel Romero, Stanislav Zivny (University of Oxford) -
1-factorizations of pseudorandom graphs
Authors: Asaf Ferber, Vishesh Jain (MIT) -
Non-black-box Worst-case to Average-case Reductions within NP
Authors: Shuichi Hirahara (The University of Tokyo) -
Metric Sublinear Algorithms via Linear Sampling
Authors: Hossein Esfandiari, Michael Mitzenmacher (Harvard SEAS) -
An Improved Bound for Weak Epsilon-Nets in the Plane
Authors: Natan Rubin (Ben-Gurion University of The Negev) -
On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
Authors: Dániel Marx (Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Hungary); Marcin Pilipczuk, Michał Pilipczuk (Institute of Informatics, University of Warsaw, Poland) -
Simple Optimal Hitting Sets for Small-Success RL
Authors: William M. Hoza, David Zuckerman (University of Texas at Austin) -
Perfect $L_p$ Sampling in a Data Stream
Authors: Rajesh Jayaram, David P. Woodruff (Carnegie Mellon University) -
Classical Verification of Quantum Computations
Authors: Urmila Mahadev (UC Berkeley) -
0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms
Authors: Yoichi Iwata (National Institute of Informatics); Yutaro Yamaguchi (Osaka University); Yuichi Yoshida (National Institute of Informatics) -
Counting t-cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems
Authors: Oded Goldreich, Guy N. Rothblum (Weizmann Institute of Science) -
ε-Coresets for Clustering (with Outliers) in Doubling Metrics
Authors: Lingxiao Huang (École polytechnique fédérale de Lausanne); Shaofeng H.-C. Jiang (The Weizmann Institute of Science); Jian Li, Xuan Wu (Tsinghua University) -
A Short List of Equalities Induces Large Sign Rank
Authors: Arkadev Chattopadhyay, Nikhil Mande (TIFR, Mumbai) -
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs
Authors: Aryeh Grinberg, Ronen Shaltiel (University of Haifa); Emanuele Viola (Northeastern University) -
Computational Two-Party Correlation
Authors: Iftach Haitner (Tel Aviv University); Ronen Shaltiel, Jad Silbak (University of Haifa); Kobbi Nissim (Georgetown University); Eran Omri (Ariel University) -
Learning Sums of Independent Random Variables with Sparse Collective Support
Authors: Anindya De (Northwestern University); Philip M. Long (Google); Rocco Servedio (Columbia University) -
A Faster Distributed Single-Source Shortest Paths Algorithm
Authors: Sebastian Krinninger (University of Salzburg); Danupon Nanongkai (KTH Royal Institute of Technology) -
An ETH-Tight Exact Algorithm for Euclidean TSP
Authors: Mark de Berg (Eindhoven University of Technology); Hans L. Bodlaender (Utrecht University and Eindhoven University of Technology); Sándor Kisfaludi-Bak, Sudeshna Kolay (Eindhoven University of Technology) -
Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
Authors: Amos Beimel (Ben Gurion University); Iftach Haitner, Nikolaos Makriyannis (Tel Aviv University); Eran Omri (Ariel University) -
A Faster Isomorphism Test for Graphs of Small Degree
Authors: Martin Grohe, Daniel Neuen (RWTH Aachen University); Pascal Schweitzer (TU Kaiserslautern) -
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time
Authors: Jatin Batra, Amit Kumar, Naveen Garg (IIT Delhi) -
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Authors: Alessandro Chiesa (UC Berkeley); Michael A. Forbes (University of Illinois at Urbana-Champaign); Tom Gur, Nicholas Spooner (UC Berkeley) -
*Low-degree testing for quantum states, and a quantum entangled games PCP for QMA *
Authors: Anand Natarajan (MIT); Thomas Vidick (Caltech) -
Contextual Search via Intrinsic Volumes
Authors: Renato Paes Leme (Google Research); Jon Schneider (Princeton University) -
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion
Authors: Subhash Khot (New York University); Dor Minzer, Muli Safra (Tel-Aviv University) -
Efficiently Learning Mixtures of Mallows Models
Authors: Allen Liu, Ankur Moitra (MIT) -
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
Authors: Zvika Brakerski (Weizmann Institute of Science); Paul Christiano (OpenAI); Urmila Mahadev, Umesh Vazirani (UC Berkeley); Thomas Vidick (California Institute of Technology) -
Spectral Subspace Sparsification
Authors: Huan Li (School of Computer Science, Fudan University); Aaron Schild (Electrical Engineering and Computer Science, University of California, Berkeley) -
The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization
Authors: Yannai A. Gonczarowski (Hebrew University of Jerusalem, Microsoft Research); S. Matthew Weinberg (Princeton University) -
Classical Homomorphic Encryption for Quantum Circuits
Authors: Urmila Mahadev (UC Berkeley) -
Holder Homeomorphisms and Approximate Nearest Neighbors
Authors: Alexandr Andoni (Columbia University); Assaf Naor (Princeton University); Aleksandar Nikolov (University of Toronto); Ilya Razenshteyn (Microsoft Research Redmond); Erik Waingarten (Columbia University) -
Dynamic filtrations and the randomized k-server conjecture
Authors: James R. Lee (University of Washington) -
Near-Optimal Approximate Decremental All Pairs Shortest Paths
Authors: Shiri Chechik (Tel-Aviv University) -
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Authors: Diptarka Chakraborty, Debarati Das (Computer Science Institute of Charles University, Prague); Elazar Goldenberg (The Academic College Of Tel Aviv-Yaffo, School of Computer Science, Tel Aviv-Yaffo); Michal Koucky (Computer Science Institute of Charles University, Prague); Michael Saks (Department of Mathematics, Rutgers University, NJ) -
Parallel Graph Connectivity in Log Diameter Rounds
Authors: Alexandr Andoni (Columbia University); Zhao Song (Harvard University & UT-Austin); Clifford Stein (Columbia University); Zhengyu Wang (Harvard University); Peilin Zhong (Columbia University) -
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Authors: Pranjal Awasthi (Rutgers University); Aravindan Vijayaraghavan (Northwestern University) -
On Derandomizing Local Distributed Algorithms
Authors: Mohsen Ghaffari (ETH Zurich); David Harris (University of Maryland); Fabian Kuhn (University of Freiburg) -
Planar Graph Perfect Matching is in N
Authors: Nima Anari (Stanford University); Vijay V. Vazirani (University of California, Irvine) -
Non-Malleable Codes for Small-Depth Circuits
Authors: Marshall Ball (Columbia University); Dana Dachman-Soled (University of Maryland); Siyao Guo (Northeastern University); Tal Malkin (Columbia University); Li-Yang Tan (Stanford University) -
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Authors: Suryajith Chillara, Christian Engels, Nutan Limaye (Department of CSE, IIT Bombay); Srikanth Srinivasan (Department of Mathematics, IIT Bombay) -
An End-to-end Argument in Mechanism Design (Prior-independent Auctions for Budgeted Agents)
Authors: Yiding Feng, Jason D. Hartline (Northwestern University) -
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Authors: Mika Göös, Aviad Rubinstein (Harvard) -
EPTAS for Max Clique on Disks and Unit Balls
Authors: Marthe Bonamy (LaBRI, Université de Bordeaux); Édouard Bonnet (ENS Lyon, LIP); Nicolas Bousquet (G-SCOP laboratory, Grenoble-INP); Pierre Charbit (Université Paris Diderot, IRIF); Stéphan Thomassé (ENS Lyon, LIP) -
Classical lower bounds from quantum upper bounds
Authors: Shalev Ben-David (University of Maryland); Adam Bouland (University of California, Berkeley); Ankit Garg, Robin Kothari (Microsoft Research) -
Sublinear algorithms for local graph centrality estimation
Authors: Marco Bressan (Sapienza University of Rome); Enoch Peserico, Luca Pretto (University of Padova) -
Laconic Function Evaluation and Applications
Authors: Willy Quach (Northeastern University); Hoeteck Wee (CNRS and ENS); Daniel Wichs (Northeastern University) -
Finding forbidden minors in sublinear time: an $n^{1/2 + o(1)}$-query one-sided tester for minor closed properties
Authors: Akash Kumar (Purdue University); C. Seshadhri, Andrew Stolman (University of California, Santa Cruz) -
Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and their Applications)
Authors: Justin Holmgren, Alex Lombardi (MIT) -
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
Authors: Christian Sohler (TU Dortmund); David P. Woodruff (CMU) -
Pseudorandom Generators for Read-Once Branching Programs, in any Order
Authors: Michael A. Forbes, Zander Kelley (University of Illinois at Urbana-Champaign) -
Quantum algorithm for simulating real time evolution of lattice Hamiltonians
Authors: Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low (Microsoft Research) -
Delegating Computations with (almost) Minimal Time and Space Overhead
Authors: Justin Holmgren (MIT); Ron D. Rothblum (MIT and Northeastern University) -
Beating the integrality ratio for s-t-tours in graphs
Authors: Vera Traub, Jens Vygen (University of Bonn) -
Improved decoding of Folded Reed-Solomon and Multiplicity Codes
Authors: Swastik Kopparty (Rutgers University); Noga Ron-Zewi (Haifa University); Shubhangi Saraf (Rutgers University); Mary Wootters (Stanford University) -
Efficient Density Evaluation for Smooth Kernels
Authors: Arturs Backurs (MIT); Moses Charikar (Stanford University); Piotr Indyk (MIT); Paris Siminelakis (Stanford University) -
Recharging Bandits
Authors: Robert Kleinberg (Cornell University); Nicole Immorlica (Microsoft Research) -
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree Authors: Vishwas Bhargava, Shubhangi Saraf (Rutgers University); Ilya Volkovich (University of Michigan)
-
PanORAMa: Oblivious RAM with Logarithmic Overhead
Authors: Sarvar Patel (Google); Giuseppe Persiano (Google and University of Salerno); Mariana Raykova (Google and Yale University); Kevin Yeo (Google) -
Random Order Contention Resolution Schemes
Authors: Marek Adamczyk, Michał Włodarczyk (University of Warsaw) -
The diameter of the fractional matching polytope and its hardness implications
Authors: Laura Sanità (University of Waterloo) -
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Authors: Matthew Fahrbach (Georgia Tech); Gary L. Miller (Carnegie Mellon University); Richard Peng, Saurabh Sawlani (Georgia Tech); Junxing Wang (Carnegie Mellon University); Shen Chen Xu (Facebook) -
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Authors: Josh Alman, Virginia Vassilevska Williams (MIT) -
Faster Exact and Approximate Algorithms for k-Cut
Authors: Anupam Gupta (Carnegie Mellon University); Euiwoong Lee (New York University); Jason Li (Carnegie Mellon University) -
Balancing Vectors in Any Norms
Authors: Daniel Dadush (CWI); Aleksandar Nikolov (University of Toronto); Kunal Talwar (Google Brain); Nicole Tomczak-Jaegermann (University of Alberta) -
Hardness Magnification for Natural Problems
Authors: Igor Carboni Oliveira, Rahul Santhanam (University of Oxford) -
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
Authors: Rasmus Kyng (Harvard University); Zhao Song (Harvard University & UT-Austin) -
The Sketching Complexity of Graph and Hypergraph Counting
Authors: John Kallaugher (UT Austin); Michael Kapralov (EPFL); Eric Price (UT Austin) -
Testing Graph Clusterability: Algorithms and Lower Bounds
Authors: Ashish Chiplunkar, Michael Kapralov (EPFL); Sanjeev Khanna (University of Pennsylvania); Aida Mousavifar (EPFL); Yuval Peres (Microsoft Research Redmond) -
Constant overhead quantum fault tolerance with quantum expander codes
Authors: Omar Fawzi (ENS de Lyon); Antoine Grospellier, Anthony Leverrier (Inria) -
Privacy Amplification by Iteration
Authors: Vitaly Feldman, Ilya Mironov, Kunal Talwar (Google); Abhradeep Thakurta (UC Santa Cruz) -
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Authors: Maria-Florina Balcan, Travis Dick, Ellen Vitercik (Carnegie Mellon University) -
Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes
Authors: Peter Burgisser (Technische Universität Berlin); Cole Franks (Rutgers University); Ankit Garg (Microsoft Research New England); Rafael Oliveira (University of Toronto); Michael Walter (QuSoft, Korteweg-de Vries Institute for Mathematics, Institute of Physics, and Institute for Logic, Language and Computation, University of Amsterdam); Avi Wigderson (Institute for Advanced Study, Princeton) -
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Authors: Michael B. Cohen, Jonathan Kelner (MIT); Rasmus Kyng (Yale University); John Peebles (MIT); Richard Peng (Georgia Tech); Anup Rao (Adobe Research); Aaron Sidford (Stanford University) -
Near log-convexity of measured heat in (discrete) time and consequences
Authors: Mert Saglam (University of Washington) -
Revealing network structure, confidentially: Improved Rates for Node-private Graphon Estimation
Authors: Christian Borgs, Jennifer Chayes (Microsoft Research); Adam Smith (Boston University); Ilias Zadik (MIT) -
Efficient polynomial-time approximation scheme for the genus of dense graphs
Authors: Yifan Jing, Bojan Mohar (Simon Fraser University) -
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
Authors: Nima Anari (Stanford University); Shayan Oveis Gharan (University of Washington); Cynthia Vinzant (North Carolina State University) -
Efficient Statistics, in High Dimensions, from Truncated Samples
Authors: Constantinos Daskalakis, Themis Gouleakis (MIT); Christos Tzamos (Microsoft Research); Manolis Zampetakis (MIT) -
PPP-Completeness with Connections to Cryptography
Authors: Katerina Sotiraki, Manolis Zampetakis (MIT); Giorgos Zirdelis (Northeastern University) -
Coordinate Methods for Accelerating $\ell_\infty$ Regression and Faster Approximate Maximum Flow
Authors: Aaron Sidford, Kevin Tian (Stanford University) -
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
Authors: Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu (Johns Hopkins University) -
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Authors: Timothy Chu (Carnegie Mellon); Yu Gao, Richard Peng (Georgia Tech); Sushant Sachdeva (University of Toronto); Saurabh Sawlani (Georgia Tech); Junxing Wang (Carnegie Mellon) -
Approximating the Permanent of a Random Matrix with Vanishing Mean
Authors: Lior Eldar; Saeed Mehraban (MIT)