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