Accepted Papers

• Shortest Paths without a Map, but with an Entropic Regularizer.
  Sebastien Bubeck (Microsoft Research), Christian Coester (University of Sheffield), Yuval Rabani (Hebrew University).
  
  
• Online List Labeling: Breaking the $\log^2 n$ Barrier.
  Michael A. Bender (Stony Brook University), Alex Conway (VMWare Research), Martin Farach-Colton (Rutgers University), Hanna Komlos (Rutgers University), William Kuszmaul (MIT), Nicole Wein (DIMACS).
  
  
• Simple Hard Instances for Low-Depth Algebraic Proofs.
  Nashlen Govindasamy (Imperial College London), Tuomas Hakoniemi (Imperial College London), Iddo Tzameret (Imperial College London).
  
  
• Constant Approximation of Min-Distances in Near-Linear Time.
  Shiri Chechik (Tel Aviv University), Tianyi Zhang (Tel Aviv University).
  
  
• First Price Auction is 1 - 1 / e^2 Efficient.
  Yaonan Jin (Columbia University), Pinyan Lu (Shanghai University of Finance and Economics).
  
  
• Estimating the Longest Increasing Subsequence in Nearly Optimal Time.
  Alexandr Andoni (Columbia University), Negev Shekel Nosatzki (Columbia University), Sandip Sinha (Columbia University), Clifford Stein (Columbia University).
  
  
• Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design.
  Bo Peng (ITCS, Shanghai University of Finance and Economics), Zhihao Gavin Tang (ITCS, Shanghai University of Finance and Economics).
  
  
• Using invariant theory to fool polynomials.
  Harm Derksen (Northeastern University), Emanuele Viola (Northeastern University).
  
  
• The Implicit Graph Conjecture is False.
  Hamed Hatami (McGill University), Pooya Hatami (Ohio State University).
  
  
• Cut Query Algorithms with Star Contraction.
  Yuval Efron (Columbia University), Danupon Nanongkai (University of Copenhagen & KTH), Sagnik Mukhopadhyay (University of Sheffield), Simon Apers (CNRS IRIF), Troy Lee (University of Technology Sydney), Pawel Gawrychowski (University of Wrocław).
  
  
• Improved Optimal Testing Results from Global Hypercontractivity.
  Tali Kaufman (Bar Ilan University), Dor Minzer (MIT).
  
  
• A Hash Table Without Hash Functions, and How to Get the Most out of Your Random Bits.
  William Henry Kuszmaul (Massachusetts Institute of Technology (MIT)).
  
  
• Balanced Allocations: The Heavily Loaded Case with Deletions.
  Nikhil Bansal (University of Michigan), William Kuszmaul (MIT).
  
  
• A Characterization of Multiclass Learnability.
  Nataly Brukhim (Princeton University), Daniel Carmon (Technion), Irit Dinur (Weizmann), Shay Moran (Technion and Google), Amir Yehudayoff (Technion-IIT).
  
  
• Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures.
  Virginia Vassilevska Williams (Massachusetts Institute of Technology), Eyob Woldeghebriel (Massachusetts Institute of Technology), Yinzhan Xu (Massachusetts Institute of Technology).
  
  
• Derandomizing Directed Random Walks in Almost-Linear Time.
  Rasmus Kyng (ETH Zurich, Department of Computer Science), Simon Meierhans (ETH Zurich, Department of Computer Science), Maximilian Probst Gutenberg (ETH Zurich, Department of Computer Science).
  
  
• Sparse random hypergraphs: Non-backtracking spectra and community detection.
  Ludovic Stephan (École Polytechnique Fédérale de Lausanne), Yizhe Zhu (University of California, Irvine).
  
  
• Killing a Vortex.
  Dimitrios Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France), Sebastian Wiederrecht (LIRMM, Univ Montpellier, CNRS, Montpellier, France).
  
  
• Low Treewidth Embeddings of Planar and Minor-Free Metrics.
  Hung Le (University of Massachusetts), Arnold Filtser (Bar-Ilan University).
  
  
• Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues.
  Tsz Chiu Kwok (Shanghai University of Finance and Economics), Lap Chi Lau (University of Waterloo), Kam Chuen Tung (University of Waterloo).
  
  
• Algorithms for the ferromagnetic Potts model on expanders.
  Charlie Carlson (University of Colorado, Boulder), Ewan Davies (University of Colorado, Boulder), Nicolas Fraiman (University of North Carolina at Chapel Hill), Alexandra Kolla (University of Colorado, Boulder and University of California Santa Cruz), Aditya Potukuchi (University of Illinois at Chicago), Corrine Yap (Rutgers University).
  
  
• Nearly Optimal Communication and Query Complexity of Bipartite Matching.
  Joakim Blikstad (KTH Royal Institute of Technology), Jan van den Brand (Simons Institute and UC Berkeley), Yuval Efron (Columbia University USA), Sagnik Mukhopadhyay (University of Sheffield UK), Danupon Nanongkai (University of Copenhagen & KTH).
  
  
• Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures.
  Aparna Gupte (MIT CSAIL), Neekon Vafa (MIT CSAIL), Vinod Vaikuntanathan (MIT CSAIL).
  
  
• Verifiable Quantum Advantage without Structure.
  Takashi Yamakawa (NTT Social Informatics Laboratories), Mark Zhandry (Princeton University and NTT Research).
  
  
• Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits.
  Pranjal Dutta (Chennai Mathematical Institute), Nitin Saxena (Department of Computer Science & Engg., Indian Institute of Technology Kanpur).
  
  
• Fitting Metrics and Ultrametrics with Minimum Disagreements.
  Vincent Cohen-Addad (Google), Chenglin Fan (Sorbonne Université, Paris, France), Euiwoong Lee (University of Michigan), Arnaud de Mesmay (CNRS, LIGM, Université Gustave Eiffel).
  
  
• Algorithms and Barriers in the Symmetric Binary Perceptron Model.
  David Gamarnik (MIT), Eren Can Kizildag (MIT), Will Perkins (University of Illinois at Chicago), Changji Xu (Harvard).
  
  
• Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Outdegree Ordering, and Densest Subgraphs.
  Laxman Dhulipala (Google Research), Quanquan C. Liu (Northwestern University), Sofya Raskhodnikova (Boston University), Jessica Shi (Massahusetts Institute of Technology), Julian Shun (Massahusetts Institute of Technology), Shangdi Yu (Massachusetts Institute of Technology).
  
  
• What is in #P and what is not?.
  Christian Ikenmeyer (University of Liverpool), Igor Pak (University of California, Los Angeles).
  
  
• Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization.
  Ahmed El Alaoui (Cornell University), Andrea Montanari (Stanford University), Mark Sellke (Stanford University).
  
  
• The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut.
  John Kallaugher (Sandia National Laboratories), Ojas Parekh (Sandia National Laboratories).
  
  
• Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds.
  Manik Dhar (Princeton University), Zeev Dvir (Princeton University).
  
  
• High-Dimensional Geometric Streaming in Polynomial Space.
  David P. Woodruff (Carnegie Mellon University), Taisuke Yasuda (Carnegie Mellon University).
  
  
• Active Linear Regression for $\ell_p$ Norms and Beyond.
  Cameron Musco (University of Massachusetts Amherst), Christopher Musco (New York University), David P. Woodruff (Carnegie Mellon University), Taisuke Yasuda (Carnegie Mellon University).
  
  
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses.
  Brice Huang (Massachusetts Institute of Technology), Mark Sellke (Stanford University).
  
  
• Correlation Clustering with Sherali-Adams.
  Vincent Cohen-Addad (Google Research), Euiwoong Lee (University of Michigan), Alantha Newman (Laboratoire G-SCOP (CNRS, Grenoble-INP)).
  
  
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation.
  Baihe Huang (Peking University), Shunhua Jiang (Columbia University), Zhao Song (Adobe Research), Runzhou Tao (Columbia University), Ruizhe Zhang (The University of Texas at Austin).
  
  
• Planting Undetectable Backdoors in Machine Learning Models.
  Shafi Goldwasser (UC Berkeley), Michael P. Kim (UC Berkeley), Vinod Vaikuntanathan (MIT), Or Zamir (IAS).
  
  
• Bounded depth proof for Tseitin formulas on the grid; revisited.
  Johan Håstad (KTH Royal Institute of Technology), Kilian Risse (KTH Royal Institute of Technology).
  
  
• Local Computation of Maximal Independent Set.
  Mohsen Ghaffari (MIT).
  
  
• Survivable Network Design Revisited: Group-Connectivity.
  Qingyun Chen (University of California, Merced), Bundit Laekhanukit (Shanghai University of Finance and Economics), Chao Liao (Huawei TCS Lab), Yuhao Zhang (Shanghai Jiao Tong University).
  
  
• Induced Cycles and Paths Are Harder Than You Think.
  Mina Dalirrooyfard (Massachusetts Institute of Technology), Virginia Vassilevska Williams (Massachusetts Institute of Technology).
  
  
• Binary Codes with Resilience Beyond 1/4 via Interaction.
  Klim Efremenko (Ben-Gurion University), Gillat Kol (Princeton University), Raghuvansh Saxena (Microsoft Research), Zhijun Zhang (Princeton University).
  
  
• Negative-Weight Single-Source Shortest Paths in Near-Linear Time.
  Aaron Bernstein (Rutgers University), Danupon Nanongkai (University of Copenhagen), Christian Wulff-Nilsen (University of Copenhagen).
  
  
• Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits.
  Ronen Shaltiel (University of Haifa), Jad Silbak (Tel Aviv University).
  
  
• Polynomial-Time Power-Sum Decomposition of Polynomials.
  Mitali Bafna (Harvard University), Jun-Ting Hsieh (Carnegie Mellon University), Pravesh Kothari (CMU), Jeff Xu (Carnegie Mellon University).
  
  
• Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring.
  Gil Cohen (Tel Aviv University), Tal Yankovitz (Tel Aviv University).
  
  
• Improved Lower Bounds for Submodular Function Minimization.
  Deeparnab Chakrabarty (Dartmouth College), Andrei Graur (Stanford University), Haotian Jiang (University of Washington), Aaron Sidford (Stanford University).
  
  
• On the Range Avoidance Problem for Circuits.
  Hanlin Ren (University of Oxford), Rahul Santhanam (University of Oxford), Zhikun Wang (Xi'an Jiaotong University).
  
  
• Near-Optimal Deterministic Vertex-Failure Connectivity Oracles.
  Yaowei Long (University of Michigan), Thatchaphol Saranurak (University of Michigan).
  
  
• Solving the Hamilton Cycle problem fast on average.
  Michael Anastos (Institute of Science and Technology Austria).
  
  
• Properly learning monotone functions via local correction.
  Jane Lange (MIT), Ronitt Rubinfeld (MIT), Arsen Vasilyan (MIT).
  
  
• Punctured Low-Bias Codes Behave Like Random Linear Codes.
  Venkatesan Guruswami (UC Berkeley), Jonathan Mosheiff (Ben-Gurion University).
  
  
• Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification.
  Fernando Granha Jeronimo (Institute of Advanced Study), Tushant Mittal (University of Chicago), Sourya Roy (University of California, Riverside), Avi Wigderson (Institute for Advanced Study).
  
  
• Sampling Lovasz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time.
  Kun He (Chinese Academy of Sciences), Chunyang Wang (Nanjing University), Yitong Yin (Nanjing University).
  
  
• Testing Positive Semidefiniteness Using Linear Measurements.
  Deanna Needell (University of California Los Angeles), William Swartworth (University of California Los Angeles), David P Woodruff (CMU).
  
  
• Hardness Self-Amplification from Feasible Hard-Core Sets.
  Shuichi Hirahara (National Institute of Informatics), Nobutaka Shimizu (Tokyo Institute of Technology).
  
  
• Õ(n + poly(k))-time Algorithm for Distance k Tree Edit Distance.
  Debarati Das (Penn State University), Jacob Gilbert (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland), Tomasz Kociumaka (UC Berkeley), Barna Saha (University of California San Diego), Hamed Saleh (University of Maryland).
  
  
• Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles.
  Mina Dalirooyfard (MIT), Ce Jin (MIT), Virginia Vassilevska Williams (MIT), Nicole Wein (DIMACS).
  
  
• Radical Sylvester-Gallai Theorem for Cubics.
  Rafael Oliveira (University of Waterloo), Akash Kumar Sengupta (Columbia University).
  
  
• Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares.
  Max Hopkins (UCSD), Ting-Chun Lin (UCSD, Hong Hai Research Institute).
  
  
• Factorial Lower Bounds for (Almost) Random Order Streams.
  Ashish Chiplunkar (IIT Delhi), John Kallaugher (Sandia National Labs), Michael Kapralov (EPFL), Eric Price (The University of Texas at Austin).
  
  
• Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing.
  Namiko Matsumoto (UC San Diego), Arya Mazumdar (UC San Diego).
  
  
• Optimal mixing for two-state anti-ferromagnetic spin systems.
  Xiaoyu Chen (Nanjing University), Weiming Feng (University of Edinburgh), Yitong Yin (Nanjing University), Xinyuan Zhang (Nanjing University).
  
  
• Determinant Maximization via Matroid Intersection Algorithms.
  Adam Brown (Georgia Insittute of Technology), Aditi Laddha (Georgia Insittute of Technology), Madhusudhan Pittu (Carnegie Mellon University), Mohit Singh (Georgia Insittute of Technology), Prasad Tetali (Carnegie Mellon University).
  
  
• Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time.
  Amir Abboud (Weizmann Institute of Science), Robert Krauthgamer (Weizmann Institute of Science), Jason Li (UC Berkeley), Debmalya Panigrahi (Duke University), Thatchaphol Saranurak (University of Michigan), Ohad Trabelsi (University of Michigan).
  
  
• Generalised entropy accumulation.
  Tony Metger (ETH Zurich), Omar Fawzi (ENS Lyon), David Sutter (IBM Quantum, IBM Research Zurich), Renato Renner (ETH Zurich).
  
  
• Localization schemes: A framework for proving mixing bounds for Markov chains.
  Yuansi Chen (Duke University), Ronen Eldan (Microsoft Research).
  
  
• A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D.
  Marvin Künnemann (TU Kaiserslautern).
  
  
• Fast Deterministic Fully Dynamic Distance Approximation.
  Jan van den Brand (Simons Institute and UC Berkeley), Sebastian Forster (University of Salzburg), Yasamin Nazari (University of Salzburg).
  
  
• On Weighted Graph Sparsification by Linear Sketching.
  Yu Chen (University of Pennsylvania), Sanjeev Khanna (University of Pennsylvania), Huan Li (University of Pennsylvania).
  
  
• Faster Pattern Matching under Edit Distance.
  Panagiotis Charalampopoulos (Reichman University, Herzliya, Israel and Birkbeck, University of London), Tomasz Kociumaka (UC Berkeley and Max Planck Institute for Informatics, SIC, Germany), Philip Wellnitz (Max Planck Institute for Informatics, SIC, Germany).
  
  
• NP-Hardness of Learning Programs and Partial MCSP.
  Shuichi Hirahara (National Institute of Informatics).
  
  
• An Approximate Generalization of the Okamura-Seymour Theorem.
  Nikhil Kumar (Hasso Plattner Institute Potsdam).
  
  
• Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
  Elazar Goldenberg (The Academic College of Tel Aviv-Yafo), Tomasz Kociumaka (UC Berkeley), Robert Krauthgamer (Weizmann Institute of Science), Barna Saha (University of California San Diego).
  
  
• On Matrix Multiplication and Polynomial Identity Testing.
  Robert Andrews (University of Illinois Urbana-Champaign).
  
  
• Streaming Facility Location in High Dimension via Geometric Hashing.
  Artur Czumaj (University of Warwick), Shaofeng Jiang (Peking University), Robert Krauthgamer (Weizmann Institute of Science), Pavel Veselý (Charles University), Mingwei Yang (Peking University).
  
  
• Memory Bounds for Continual Learning.
  Binghui Peng (Columbia), Christos Papadimitriou (Columbia University), Xi Chen (Columbia University).
  
  
• Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications.
  Michael Elkin (Ben-Gurion University of the Negev), Bernhard Haeupler (ETHZ & Carnegie Mellon University), Václav Rozhoň (ETH Zurich), Christoph Grunau (ETH Zurich).
  
  
• Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets.
  Shimon Kogan (Weizmann Institute), Merav Parter (Weizmann Institute).
  
  
• Strong XOR Lemma for Communication with Bounded Rounds.
  Huacheng Yu (Princeton University).
  
  
• Quantum Tanner codes.
  Anthony Leverrier (Inria), Gilles Zemor (University of Bordeaux).
  
  
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states.
  Jeongwan Haah (Microsoft Research), Robin Kothari (Microsoft), Ewin Tang (University of Washington).
  
  
• Motif Cut Sparsifiers.
  Michael Kapralov (EPFL), Mikhail Makarov (EPFL), Sandeep Silwal (MIT), Christian Sohler (University of Cologne), Jakab Tardos (EPFL).
  
  
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.
  Li Chen (Georgia Tech), Rasmus Kyng (ETH Zurich), Yang P. Liu (Stanford University), Richard Peng (University of Waterloo), Maximilian Probst Gutenberg (ETH Zurich), Sushant Sachdeva (University of Toronto).
  
  
• Minimax Rates for Robust Community Detection.
  Allen Liu (MIT), Ankur Moitra (Math & CSAIL, MIT).
  
  
• Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably).
  Alex Lombardi (MIT), Fermi Ma (Simons Institute and UC Berkeley), Nicholas Spooner (University of Warwick).
  
  
• Interior point methods are not worse than Simplex.
  Xavier Allamigeon (INRIA & Ecole Polytechnique), Daniel Dadush (CWI Amsterdam), Georg Loho (University of Twente), Bento Natura (London School of Economics and Political Science), László A. Végh (London School of Economics and Political Science).
  
  
• A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.
  Anna Karlin (University of Washington), Nathan Klein (University of Washington), Shayan Oveis Gharan (University of Washington).
  
  
• Tight Bounds for Quantum State Certification with Incoherent Measurements.
  Sitan Chen (UC Berkeley), Brice Huang (MIT), Jerry Li (Microsoft Research), Allen Liu (MIT).
  
  
• Fast Multivariate Multipoint Evaluation Over All Finite Fields.
  Vishwas Bhargava (Rutgers University), Sumanta Ghosh (Caltech), Zeyu Guo (UT Austin), Mrinal Kumar (IIT Bombay), Chris Umans (Caltech).
  
  
• Rate-1 Non-Interactive Arguments for Batch-NP and Applications.
  Lalita Devadas (MIT CSAIL), Rishab Goyal (MIT CSAIL), Yael Tauman Kalai (MIT and Microsoft Research), Vinod Vaikuntanathan (MIT CSAIL).
  
  
• Separations in Proof Complexity and TFNP.
  Mika Göös (EPFL), Alexandros Hollender (University of Oxford), Siddhartha Jain (EPFL), Gilbert Maystre (EPFL), William Pires (McGill), Robert Robere (McGill), Ran Tao (McGill).
  
  
• Randomised Composition and Small-Bias Minimax.
  Shalev Ben-David (University of Waterloo), Eric Blais (University of Waterloo), Mika Göös (EPFL), Gilbert Maystre (EPFL).
  
  
• Incrementally Verifiable Computation via Rate-1 Batch Arguments.
  Omer Paneth (Tel Aviv University), Rafael Pass (Cornell Tech and Tel Aviv University).
  
  
• Unstructured Hardness to Average-Case Randomness.
  Lijie Chen (MIT), Ron Rothblum (Technion), Roei Tell (IAS + DIMACS).
  
  
• New Additive Spanner Lower Bounds by an Unlayered Obstacle Product.
  Greg Bodwin (University of Michigan), Gary Hoppenworth (University of Michigan).
  
  
• The Power of Uniform Sampling for Coresets.
  Vladimir Braverman (Johns Hopkins University), Vincent Cohen-Addad (Google Research, Switzerland), Shaofeng Jiang (Peking University), Robert Krauthgamer (Weizmann Institute of Science), Chris Schwiegelshohn (Aarhus University), Mads Bech Toftrup (Aarhus University), Xuan Wu (Johns Hopkins University).
  
  
• Geometry of Secure Two-party Computation.
  Saugata Basu (Purdue University), Hamidreza Amini Khorasgani (Purdue University), Hemanta K. Maji (Purdue University), Hai H. Nguyen (Purdue University).
  
  
• Computing in Anonymous Dynamic Networks Is Linear.
  Giuseppe Antonio Di Luna (Sapienza University of Rome), Giovanni Viglietta (Japan Advanced Institute of Science and Technology (JAIST)).
  
  
• Classical Verification of Quantum Computations in Linear Time.
  Jiayu Zhang (California Institute of Technology).
  
  
• Pure-Circuit: Strong Inapproximability for PPAD.
  Argyrios Deligkas (Royal Holloway, University of London), John Fearnley (University of Liverpool), Alexandros Hollender (University of Oxford), Themistoklis Melissourgos (University of Essex).
  
  
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models.
  Joao Basso (Google), David Gamarnik (MIT), Song Mei (University of California, Berkeley), Leo Zhou (California Institute of Technology).
  
  
• Rounds vs Communication Tradeoffs for Maximal Independent Sets.
  Sepehr Assadi (Rutgers University), Gillat Kol (Princeton University), Zhijun Zhang (Princeton University).
  
  
• Almost 3-Approximate Correlation Clustering in Constant Rounds.
  Soheil Behnezhad (Stanford University), Moses Charikar (Stanford University), Weiyun Ma (Stanford University), Li-Yang Tan (Stanford University).
  
  
• Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography.
  Alexander Meiburg (UCSB).
  
  
• A Proof of the Kahn-Kalai Conjecture.
  Huy Tuan Pham (Stanford University), Jinyoung Park (Stanford University).
  
  
• Deterministic Small Vertex Connectivity in Almost Linear Time.
  Thatchaphol Saranurak (University of Michigan), Sorrachai Yingchareonthawornchai (Aalto University).
  
  
• Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence.
  Nima Anari (Stanford University), Yang P. Liu (Stanford University), Thuy-Duong Vuong (Stanford University).
  
  
• Indistinguishability Obfuscation via Mathematical Proofs of Equivalence.
  Abhishek Jain (Johns Hopkins University), Zhengzhong Jin (Johns Hopkins University).