Accepted papers

MDS matrices over small fields: a proof of the GMMDS 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 FarachColton (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 generalvalued CSPs seen from the other side
Authors: Clement Carbonnel, Miguel Romero, Stanislav Zivny (University of Oxford) 
1factorizations of pseudorandom graphs
Authors: Asaf Ferber, Vishesh Jain (MIT) 
Nonblackbox Worstcase to Averagecase 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 EpsilonNets in the Plane
Authors: Natan Rubin (BenGurion 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 SmallSuccess 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, HalfIntegral Apath Packing, and LinearTime FPT Algorithms
Authors: Yoichi Iwata (National Institute of Informatics); Yutaro Yamaguchi (Osaka University); Yuichi Yoshida (National Institute of Informatics) 
Counting tcliques: WorstCase to AverageCase 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 TwoParty 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 SingleSource Shortest Paths Algorithm
Authors: Sebastian Krinninger (University of Salzburg); Danupon Nanongkai (KTH Royal Institute of Technology) 
An ETHTight 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 KisfaludiBak, Sudeshna Kolay (Eindhoven University of Technology) 
Tighter Bounds on MultiParty 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 Pseudopolynomial 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 UrbanaChampaign); Tom Gur, Nicholas Spooner (UC Berkeley) 
*Lowdegree 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 NearPerfect Expansion
Authors: Subhash Khot (New York University); Dor Minzer, Muli Safra (TelAviv 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 Uptoε MultiDimensional 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 kserver conjecture
Authors: James R. Lee (University of Washington) 
NearOptimal Approximate Decremental All Pairs Shortest Paths
Authors: Shiri Chechik (TelAviv University) 
Approximating Edit Distance Within Constant Factor in Truly SubQuadratic Time
Authors: Diptarka Chakraborty, Debarati Das (Computer Science Institute of Charles University, Prague); Elazar Goldenberg (The Academic College Of Tel AvivYaffo, School of Computer Science, Tel AvivYaffo); 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 & UTAustin); 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) 
NonMalleable Codes for SmallDepth Circuits
Authors: Marshall Ball (Columbia University); Dana DachmanSoled (University of Maryland); Siyao Guo (Northeastern University); Tal Malkin (Columbia University); LiYang Tan (Stanford University) 
A NearOptimal DepthHierarchy Theorem for SmallDepth Multilinear Circuits
Authors: Suryajith Chillara, Christian Engels, Nutan Limaye (Department of CSE, IIT Bombay); Srikanth Srinivasan (Department of Mathematics, IIT Bombay) 
An Endtoend Argument in Mechanism Design (Priorindependent Auctions for Budgeted Agents)
Authors: Yiding Feng, Jason D. Hartline (Northwestern University) 
NearOptimal 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 (GSCOP laboratory, GrenobleINP); Pierre Charbit (Université Paris Diderot, IRIF); Stéphan Thomassé (ENS Lyon, LIP) 
Classical lower bounds from quantum upper bounds
Authors: Shalev BenDavid (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 onesided tester for minor closed properties
Authors: Akash Kumar (Purdue University); C. Seshadhri, Andrew Stolman (University of California, Santa Cruz) 
Cryptographic Hashing from Strong OneWay Functions (Or: OneWay Product Functions and their Applications)
Authors: Justin Holmgren, Alex Lombardi (MIT) 
Strong Coresets for kMedian and Subspace Approximation: Goodbye Dimension
Authors: Christian Sohler (TU Dortmund); David P. Woodruff (CMU) 
Pseudorandom Generators for ReadOnce Branching Programs, in any Order
Authors: Michael A. Forbes, Zander Kelley (University of Illinois at UrbanaChampaign) 
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 sttours in graphs
Authors: Vera Traub, Jens Vygen (University of Bonn) 
Improved decoding of Folded ReedSolomon and Multiplicity Codes
Authors: Swastik Kopparty (Rutgers University); Noga RonZewi (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 kCut
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 TomczakJaegermann (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 & UTAustin) 
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 DataDriven Algorithm Design, Online Learning, and Private Optimization
Authors: MariaFlorina 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, Kortewegde 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 NearlyLinear 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 logconvexity of measured heat in (discrete) time and consequences
Authors: Mert Saglam (University of Washington) 
Revealing network structure, confidentially: Improved Rates for Nodeprivate Graphon Estimation
Authors: Christian Borgs, Jennifer Chayes (Microsoft Research); Adam Smith (Boston University); Ilias Zadik (MIT) 
Efficient polynomialtime approximation scheme for the genus of dense graphs
Authors: Yifan Jing, Bojan Mohar (Simon Fraser University) 
LogConcave 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) 
PPPCompleteness 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)