Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain (MIT), Frederic Koehler (MIT), Andrej Risteski (MIT)
Algebraic approach to promise constraint satisfaction
Jakub Bulín (Charles University), Andrei Krokhin (University of Durham), Jakub Opršal (University of Durham)
Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications)
Ilias Diakonikolas (USC), Daniel Kane (UCSD)
Testing Graphs in Vertex-Distribution-Free Models
Oded Goldreich (Weizmann Institute of Science)
Solving Linear Programs in the Current Matrix Multiplication Time
Michael Cohen (MIT), Yin Tat Lee (University of Washington), Zhao Song (University of Washington & UT-Austin)
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski (Harvard University), Aviad Rubinstein (Stanford University), Yaron Singer (Harvard University)
Algorithmic Pirogov-Sinai Theory
Tyler Helmuth (University of Bristol), Will Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam)
Quantum Weak Coin Flipping
Atul Singh Arora (Université libre de Bruxelles), Jérémie Roland (Université libre de Bruxelles), Stephan Weis (Universidade de Coimbra)
Optimal terminal dimensionality reduction in Euclidean space
Shyam Narayanan (Harvard University), Jelani Nelson (Harvard University)
Which Properties are Testable in the Vertex-Distribution-Free Model
Lior Gishboliner (Tel Aviv University), Asaf Shapira (Tel Aviv University)
Non-Gaussian Component Analysis using Entropy Methods
Navin Goyal (Microsoft Research India), Abhishek Shetty (Microsoft Research India)
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang (University of Texas at Austin)
Separating Monotone VP and VNP
Amir Yehudayoff (Technion-IIT)
Private PAC learning implies finite Littlestone Dimension
Noga Alon (Princeton University), Roi Livni (Tel Aviv University), Maryanthe Malliaris (Chicago University), Shay Moran (Princeton University)
On a generalization of iterated and randomized rounding
Nikhil Bansal (CWI and TU Eindhoven)
Competitively Chasing Convex Bodies
Sebastien Bubeck (Microsoft Research), Yin Tat Lee (University of Washington), Yuanzhi Li (Stanford University), Mark Sellke (Stanford University)
Oracle Separation of BQP and PH
Ran Raz (Princeton University), Avishay Tal (Stanford University)
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos (King’s College), Paweł Gawrychowski (University of Wroclaw), Shay Mozes (IDC Herzliya), Oren Weimann (University of Haifa)
Local Decodability of the Burrows-Wheeler Transform
Sandip Sinha (Columbia University), Omri Weinstein (Columbia University)
Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti (Sapienza), Marc Bury (Zalando SE), Vincent Cohen-Addad (CNRS), Fabrizio Grandoni (IDSIA), Chris Schwiegelshohn (Sapienza)
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka (UCLA), Omer Reingold (Stanford University), Avishay Tal (Stanford University)
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Julia Chuzhoy (Toyota Technological Institute at Chicago), Sanjeev Khanna (University of Pennsylvania)
Fooling Polytopes
Ryan O'Donnell (Carnegie Mellon University), Rocco A. Servedio (Columbia University), Li-Yang Tan (Stanford University)
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty (Dartmouth College), Chaitanya Swamy (University of Waterloo)
DNF sparsification beyond sunflowers
Shachar Lovett (UC San Diego), Jiapeng Zhang (UC San Diego)
Planar Graphs of Bounded Degree have Bounded Queue Number
Michael Bekos (University of Tübingen), Henry Förster (University of Tübingen), Martin Gronemann (University of Cologne), Tamara Mchedlidze (Karlsruhe Institute of Technology), Fabrizio Montecchiani (University of Perugia), Chrysanthi Raftopoulou (National Technical University of Athens), Torsten Ueckerdt (Karlsruhe Institute of Technology)
Settling the Sample Complexity of Single-parameter Revenue Maximization
Chenghao Guo (IIIS), Zhiyi Huang (University of Hong Kong), Xinzhi Zhang (IIIS)
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein (Rutgers University), Danupon Nanongkai (KTH Royal Institute of Technology)
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen (Yale University), Moran Feldman (Open University of Israel), Amin Karbasi (Yale University)
Planar point sets determine many pairwise crossing segments
János Pach (EPFL), Natan Rubin (Ben-Gurion University), Gábor Tardos (Renyi Institute)
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
Mina Dalirrooyfard (MIT), Thuy Duong Vuong (MIT), Virginia Vassilevska Williams (MIT)
Random walks and forbidden minors II: a $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs
Akash Kumar (Purdue University), C. Seshadhri (University of California), Andrew Stolman (University of California)
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin (Department of IEDA), Pinyan Lu (ITCS), Qi Qi (Department of IEDA), Zhihao Gavin Tang (Department of Computer Science), Tao Xiao (Department of Computer Science)
Communication Complexity of Estimating Correlations
Uri Hadar (Tel Aviv University), Jingbo Liu (MIT), Yury Polyanskiy (MIT), Ofer Shayevitz (Tel Aviv University)
Bootstrapping Results for Threshold Circuits Just Beyond Known Lower Bounds
Lijie Chen (MIT), Roei Tell (Weizmann Institute of Science)
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas (Ecole Polytechnique Federale de Lausanne), Paul W. Goldberg (University of Oxford)
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein (Department of Computer Science), Maximilian Probst (Department of Computer Science), Christian Wulff-Nilsen (Department of Computer Science)
The Structure of Optimal Private Tests for Simple Hypotheses
Clement Canonne (Stanford University), Gautam Kamath (Simons Institute for the Theory of Computing), Audra McMillan (Boston University and Northeastern University), Adam Smith (Boston University), Jonathan Ullman (Northeastern University)
Lower Bounds for External Memory Sorting via Network Coding
Alireza Farhadi (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland), Kasper Green Larsen (Aarhus University), Elaine Shi (Cornell University)
A unifying method for the design of algorithms canonizing combinatorial objects
Pascal Schweitzer (TU Kaiserslautern), Daniel Wiebking (RWTH Aachen University)
A Fixed-Depth Size-Hierarchy Theorem for $AC^0[\oplus]$ via the Coin Problem
Nutan Limaye (IIT Bombay), Karteek Sreenivasaiah (IIT Hyderabad), Srikanth Srinivasan (IIT Bombay), Utkarsh Tripathi (IIT Bombay), S. Venkitesh (IIT Bombay)
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg (University of Illinois at Urbana-Champaign), László A. Végh (London School of Economics and Political Science)
Sylvester-Gallai type theorems for quadratic polynomials
Amir Shpilka (Tel-Aviv University)
Achieving Optimal Backlog in Mullti-Processor Cup Games
Michael A. Bender (Stony Brook University), Martin Farach-Colton (Rutgers University), William Kuszmaul (Massachusetts Institute of Technology)
Quantum proof systems for iterated exponential time, and beyond
Joseph Fitzsimons (Singapore University of Technology and Design), Zhengfeng Ji (University of Technology Sydney), Thomas Vidick ( CalTech ), Henry Yuen (University of Toronto)
Quantum state certification
Costin Bădescu (Carnegie Mellon University), Ryan O'Donnell (Carnegie Mellon University), John Wright (Massachusetts Institute of Technology)
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh (UC Berkeley), Qiuyi (Richard) Zhang (UC Berkeley)
Distributed Edge Connectivity in Sublinear Time
Mohit Daga (KTH Royal Institute of Technology), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute)
Bridging between 0/1 and Linear Programming via Random Walks
Joshua Brakensiek (Stanford University), Venkatesan Guruswami (Carnegie Mellon University)
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir (Princeton University), Alexander Golovnev (Harvard University), Omri Weinstein (Columbia University)
$O(\log^2k/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.
Fabrizio Grandoni (IDSIA), Bundit Laekhanukit (Shanghai University of Finance and Economics), Shi Li (University at Buffalo)
Performance of Johnson–Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev (Northwestern University), Yury Makarychev (TTIC), Ilya Razenshteyn (Microsoft Research)
Testing Unateness Nearly Optimally
Xi Chen (Columbia University), Erik Waingarten (Columbia University)
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Huacheng Yu (Harvard University)
The Log-Approximate-Rank Conjecture is False
Arkadev Chattopadhyay (School of Technology and Computer Science), Nikhil Mande (School of Technology and Computer Science), Suhail Sherif (School of Technology and Computer Science)
The Communication Complexity of Local Search
Yakov Babichenko (Technion), Shahar Dobzinski (Weizmann Institute), Noam Nisan (Hebrew University of Jerusalem)
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos (Harvard University), Zhao Song (UT-Austin)
Canonical form for graphs in quasipolynomial time
Laszlo Babai (University of Chicago)
Spectral Methods from Tensor Networks
Ankur Moitra (MIT), Alexander S. Wein (Courant Institute)
Planar Diameter via Metric Compression
Jason Li (CMU), Merav Parter (Weizmann Institute)
Faster $k$-SAT algorithms using biased-PPSZ
Thomas Dueholm Hansen (University of Copenhagen), Haim Kaplan (Tel Aviv University), Or Zamir (Tel Aviv University), Uri Zwick (Tel Aviv University)
Reconstruction of non-degenerate homogeneous depth three circuits
Neeraj Kayal (Microsoft Research India), Chandan Saha (Indian Institute of Science)
Polynomial Pass Lower bounds for Graph Streaming Algorithms
Sepehr Assadi (Princeton University), Yu Chen (University of Pennsylvania), Sanjeev Khanna (University of Pennsylvania)
Regression from Dependent Observations
Constantinos Daskalakis (MIT), Nishanth Dikkala (MIT), Ioannis Panageas (SUTD)
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron (Tel Aviv University), Michael Kapralov (École Polytechnique Fédérale de Lausanne), Cameron Musco (Microsoft Research), Christopher Musco (Princeton University), Ameya Velingker (École Polytechnique Fédérale de Lausanne), Amir Zandieh (École Polytechnique Fédérale de Lausanne)
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov (EPFL), Dmitry Krachun (University of Geneva)
Dynamic Sampling from Graphical Models
Weiming Feng (Nanjing University), Nisheeth K. Vishnoi (Yale University), Yitong Yin (Nanjing University)
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
András Gilyén (QuSoft), Yuan Su (QuICS), Guang Hao Low (QuArC), Nathan Wiebe (QuArC)
The Parallel Repetition of Non-Signaling Games: Counterexamples and Dichotomy
Justin Holmgren (Princeton University), Lisa Yang (MIT)
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa (University of Warwick), Tomasz Kociumaka (University of Warsaw and Bar-Ilan University)
The Reachability Problem for Petri Nets is Not Elementary
Wojciech Czerwinski (University of Warsaw), Slawomir Lasota (University of Warsaw), Ranko Lazic (University of Warwick), Jerome Leroux (CNRS and University of Bordeaux), Filip Mazowiecki (University of Bordeaux)
The Online k-Taxi Problem
Christian Coester (University of Oxford), Elias Koutsoupias (University of Oxford)
Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing
Bernhard Haeupler (Carnegie Mellon University), Aviad Rubinstein (Stanford University), Amirbehshad Shahrasbi (Carnegie Mellon University)
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler (MIT), Frederic Koehler (MIT), Ankur Moitra (MIT)
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann (Max Planck Institute for Informatics), Marvin Kunnemann (Max Planck Institute for Informatics), Karol Wegrzycki (University of Warsaw)
On the Approximation Resistance of Balanced Linear Threshold Functions
Aaron Potechin (University of Chicago)
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen (MIT), Ankur Moitra (MIT)
Dynamic Set Cover: Improved Algorithms & Lower Bounds
Amir Abboud (IBM Almaden Research Center), Raghavendra Addanki (University of Massachusetts Amherst), Fabrizio Grandoni (IDSIA), Debmalya Panigrahi (Duke University), Barna Saha (University of Massachusetts Amherst)
Private Selection from Private Candidates
Jingcheng Liu (UC Berkeley), Kunal Talwar (Google Brain)
Gentle Measurement of Quantum States and Differential Privacy
Scott Aaronson (University of Texas at Austin), Guy Rothblum (Weizmann Institute of Science)
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee (Georgia Tech), Yu Gao (Georgia Tech), Gramoz Goranci (University of Vienna), Richard Peng (Georgia Tech)
Fiat-Shamir: From Practice to Theory
Ran Canetti (BU), Yilei Chen (Visa Research), Justin Holmgren (Princeton), Alex Lombardi (MIT), Guy N. Rothblum (Weizmann Institute of Science), Ron D. Rothblum (Technion), Daniel Wichs (Northeastern)
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster (University of Salzburg), Gramoz Goranci (University of Vienna)
Weak Zero-Knowledge Beyond the Black-Box Barrier
Nir Bitansky (TAU), Dakshita Khurana (MSR), Omer Paneth (MIT)
Capacity lower bound for the Ising perceptron
Jian Ding (University of Pennsylvania), Nike Sun (Massachusetts Institute of Technology)
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
Thomas C. Bohdanowicz (California Institute of Technology), Elizabeth Crosson (University of New Mexico), Chinmay Nirkhe (University of California), Henry Yuen (University of Toronto)
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari (Stanford University), Kuikui Liu (University of Washington), Shayan Oveis Gharan (University of Washington), Cynthia Vinzant (North Carolina State University)
Hamiltonian simulation with nearly optimal dependence on spectral norm
Guang Hao Low (Microsoft Research)
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Omar Alrabiah (Carnegie Mellon University), Venkatesan Guruswami (Carnegie Mellon University)
$1+\epsilon$ Approximation of Tree Edit Distance in Quadratic Time
Mahdi Boroujeni (University of Maryland), Mohammad Ghodsi (University of Maryland), MohammadTaghi HajiAghayi (University of Maryland), Saeed Seddighin (University of Maryland)
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene (Boston University), Huy L. Nguyen (Northeastern University), Adrian Vladu (Boston University)
Computing Quartet Distance is Equivalent to Counting 4-Cycles
Bartłomiej Dudek (University of Wrocław), Paweł Gawrychowski (University of Wrocław)
Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions
Andre Linhares (University of Waterloo), Chaitanya Swamy (University of Waterloo)
Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight
Kun He (ICT), Qian Li (Alibaba Group), Xiaoming Sun (ICT), Jiapeng Zhang (University of California)
Towards the Locality of Vizing's Theorem
Hsin-Hao Su (Boston College), Hoa T. Vu (Boston College)
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute at Chicago), Sorrachai Yingchareonthawornchai (Michigan State University)
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Anupam Gupta (CMU), Euiwoong Lee (NYU), Jason Li (CMU)
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes
Dylan McKay (Massachusetts Institute of Technology), Cody Murray (Simons Institute), Ryan Williams (Massachusetts Institute of Technology)
On Approximating the Covering Radius and Finding Dense Lattice Subspaces
Daniel Dadush (CWI)
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar (Stanford University), Kirankumar Shiragur (Stanford University), Aaron Sidford (Stanford University)
Explicit $N$-vertex graphs with maximum degree $K$ and diameter $[1+o(1)]\log_{K-1} N$ for each $K-1$ a prime power
Michael Capalbo (CCS)
Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir
Arka Rai Choudhuri (Johns Hopkins University), Pavel Hubacek (Charles University), Chethan Kamath (IST Austria), Krzysztof Pietrzak (IST Austria), Alon Rosen (IDC Herzliya), Guy N. Rothblum (Weizmann Institute of Science)
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek (Stanford University), Sivakanth Gopi (Microsoft Research), Venkatesan Guruswami (Carnegie Mellon University)
New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search
Alessio Conte (National Institute of Informatics), Takeaki Uno (National Institute of Informatics)
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan (Stanford University), Aaron Sidford (Stanford University), Gregory Valiant (Stanford University)
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Adam Bene Watts (Massachusetts Institute of Technology), Robin Kothari (Microsoft Research), Luke Schaeffer (Massachusetts Institute of Technology), Avishay Tal (Stanford University)
Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
Hedyeh Beyhaghi (Cornell University), S. Matthew Weinberg (Princeton University)
Parallelizing greedy for submodular set function maximization in matroids and beyond
Chandra Chekuri (UIUC), Kent Quanrud (UIUC)
Why Extension-Based Proofs Fail
Dan Alistarh (IST Austria), James Aspnes (Yale University), Faith Ellen (University of Toronto), Rati Gelashvili (University of Toronto), Leqi Zhu (University of Toronto)
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
Alexander A. Sherstov (UCLA), Pei Wu (UCLA)
Polylogarithmic approximation for Euler genus on bounded degree graphs
Ken-ichi Kawarabayashi (National Institute of Informatics), Anastasios Sidiropoulos (University of Illinois at Chicago)
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng (Harvard), Richard Peng (Georgia Tech), Sushant Sachdeva (University of Toronto), Di Wang (Georgia Tech)
How to Delegate Computations Publicly
Yael Tauman Kalai (Microsoft Research), Omer Paneth (MIT), Lisa Yang (MIT)