STOC 2024: Accepted Papers

STOC 2024 Accepted Papers

Swap cosystolic expansion
Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science)

On the Pauli Spectrum of QAC⁰
Shivam Nadimpalli, Natalie Parham (Columbia University); Francisca Vasconcelos (University of California, Berkeley); Henry Yuen (Columbia University)

Influences in Mixing Measures
Frederic Koehler (Stanford University); Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer, Elchanan Mossel (MIT)

Parallel Sampling via Counting
Nima Anari, Ruiquan Gao, Aviad Rubinstein (Stanford University)

Local minima in quantum systems
Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou (California Institute of Technology)

Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee (University of Michigan); Jason Li (UC Berkeley); Thatchaphol Saranurak (University of Michigan)

Detecting Low-Degree Truncation
Anindya De, Huan Li (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University)

How Random CSPs Fool Hierarchies
Siu On Chan, Hiu Tsun Ng (The Chinese University of Hong Kong); Sijin Peng (Tsinghua University)

Fair Division via Quantile Shares
Yakov Babichenko (Technion - Israel Institute of Technology); Michal Feldman (Tel Aviv University); Ron Holzman (Technion - Israel Institute of Technology); Vishnu V. Narayan (Tel Aviv University)

Learning shallow quantum circuits
Hsin-Yuan Huang (Caltech); Yunchao Liu (UC Berkeley); Michael Broughton (Google Quantum AI); Isaac Kim (UC Davis); Anurag Anshu (Harvard University); Zeph Landau (UC Berkeley); Jarrod R. McClean (Google Quantum AI)

Prophet Inequalities with Recourse
Farbod Ekbatani, Rad Niazadeh (University of Chicago Booth School of Business); Pranav Nuti, Jan Vondrak (Stanford)

Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor (University of Cambridge); Nicholas Spooner (University of Warwick/NYU)

Black-Box PPP is Not Turing-Closed
Noah Fleming (Memorial University of Newfoundland); Stefan Grosser (McGill); Toniann Pitassi (Columbia); Robert Robere (McGill)

Commitments from Quantum One-Wayness
Dakshita Khurana (University of Illinois at Urbana-Champaign); Kabir Tomer (University of Illinois Urbana-Champaign)

Hardness Condensation by Restriction
Mika Göös (EPFL); Ilan Newman (University of Haifa); Artur Riazanov, Dmitry Sokolov (EPFL)

Product Mixing in Compact Lie Groups
David Ellis (University of Bristol); Guy Kindler, Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer (MIT)

One-Way Functions and Zero Knowledge
Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology)

Combinatorial Correlation Clustering
Vincent Cohen-Addad (Google Research, France); Marcin Pilipczuk (University of Warsaw); David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan, Hanwen Zhang (University of Copenhagen)

Batch Proofs are Statistically Hiding
Nir Bitansky (Tel Aviv University); Chethan Kamath (IIT Bombay); Omer Paneth (Tel Aviv University); Ron D. Rothblum (Technion); Prashant Nalini Vasudevan (NUS)

0-1 Knapsack in Nearly Quadratic Time
Ce Jin (MIT)

Better coloring of 3-colorable graphs
Ken-ichi Kawarabayashi (National Institute of Informatics, The University of Tokyo); Mikkel Thorup (University of Copenhagen); Hirotaka Yoneda (The University of Tokyo)

Sparsifying generalized linear models
Arun Jambulapati (Simons Institute); James R Lee (University of Washington); Yang P. Liu (Institute for Advanced Study); Aaron Sidford (Stanford University)

Bilateral Trade with Correlated Values
Shahar Dobzinski (Weizmann); Ariel Shaulker (Weizmann Institute)

Nonlinear dynamics for the Ising model
Pietro Caputo (Univ Rome III); Alistair Sinclair (U.C. Berkeley)

Optimal Online Discrepancy Minimization
Janardhan Kulkarni (Microsoft Research); Victor Reis (Institute for Advanced Study); Thomas Rothvoss (University of Washington)

Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler (ETH Zurich); D Ellis Hershkowitz (Brown University); Jason Li (UC Berkeley); Antti Röyskö (ETH Zurich); Thatchaphol Saranurak (University of Michigan)

Almost Linear Size Edit Distance Sketch
Michal Koucký (Charles University/Rutgers University); Michael Saks (Rutgers University)

Edge-Disjoint Paths in Eulerian Digraphs
Dario Giuliano Cavallaro (TU Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Stephan Kreutzer (TU Berlin)

Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma (Freie Universität Berlin); Michal Opler (Czech Technical University in Prague)

SNARGs Under LWE via Propositional Proofs
Zhengzhong Jin (MIT CSAIL); Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Princeton); Vinod Vaikuntanathan (MIT CSAIL)

Planted Clique Conjectures Are Equivalent
Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology)

A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)

Two prover perfect zero knowledge for MIP*
Kieran Mastel, William Slofstra (University of Waterloo)

Locality Bounds for Sampling Hamming Slices
Daniel M. Kane, Anthony Ostuni (UC San Diego); Kewen Wu (UC Berkeley)

Calibrated Language Models Must Hallucinate
Adam Tauman Kalai (Microsoft Research); Santosh Vempala (Georgia Tech)

Nonlocality under Computational Assumptions
Grzegorz Gluch, Khashayar Barooti (EPFL); Alexandru Gheorghiu (Chalmers University of Technology); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau)

Approximating Partition in Near-Linear Time
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)

On Approximability of Satisfiable k-CSPs: IV
Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)

Explicit two-sided unique-neighbor expanders
Jun-Ting Hsieh (Carnegie Mellon University); Theo McKenzie (Stanford University); Sidhanth Mohanty (MIT); Pedro Paredes (Princeton University)

Beating Brute Force for Compression Problems
Shuichi Hirahara (National Institute of Informatics, Tokyo, Japan); Rahul Ilango, Ryan Williams (MIT)

Nearly Optimal Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta (IIT Gandhinagar)

Private graphon estimation via sum-of-squares
Hongjie Chen, Jingqiu Ding (ETH Zürich); Tommaso D'Orsi (Bocconi University); Yiding Hua (ETH Zürich); Chih-Hung Liu (National Taiwan University); David Steurer (ETH Zürich)

Near Optimal Alphabet-Soundness Tradeoff PCPs
Dor Minzer, Kai Zhe Zheng (MIT)

Memory Checking Requires Logarithmic Overhead
Elette Boyle (Reichman University and NTT Research); Ilan Komargodski (Hebrew University and NTT Research); Neekon Vafa (MIT)

Self-Improvement for Circuit-Analysis Problems
Ryan Williams (MIT)

Structural Complexities of Matching Mechanisms
Yannai A. Gonczarowski (Harvard University); Clayton Thomas (Microsoft Research)

On the Power of Homogeneous Algebraic Formulas
Hervé Fournier (IMJ-PRG, Université Paris Cité); Nutan Limaye (IT University of Copenhagen); Srikanth Srinivasan (University of Copenhagen); Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA)

Ghost Value Augmentation for k-ECSS and k-ECSM
D Ellis Hershkowitz (Brown University); Nathan Klein (Institute for Advanced Study); Rico Zenklusen (ETH Zurich)

Relaxed Local Correctability from Local Testing
Vinayak M. Kumar, Geoffrey Mon (University of Texas at Austin)

On the Power of Interactive Proofs for Learning
Tom Gur (University of Cambridge); Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh (Simon Fraser University); Ninad Rajgopal (University of Cambridge); Bahar Salamatian, Igor Shinkar (Simon Fraser University)

Local Borsuk-Ulam, Stability, and Replicability
Zachary Chase, Bogdan Chornomaz, Shay Moran (Technion); Amir Yehudayoff (Technion-IIT)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu (MIT)

Tree Evaluation is in Space O(log n · log log n)
James Cook; Ian Mertz (University of Warwick)

Quantum State Obfuscation from Classical Oracles
James Bartusek (UC Berkeley); Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT CSAIL)

Quantum Time-Space Tradeoffs for Matrix Problems
Paul Beame (University of Washington); Niels Kornerup (University of Texas at Austin); Michael Whitmeyer (University of Washington)

Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics)

Lower bounds for regular resolution over parities
Klim Efremenko (Ben-Gurion University of the Negev); Michal Garlik (Imperial College London); Dmitry Itsykson (Ben-Gurion University of the Negev)

Data-Dependent LSH for the Earth Mover’s Distance
Rajesh Jayaram (Google Research); Erik Waingarten, Tian Zhang (University of Pennsylvania)

Packing even directed circuits quarter-integrally
Maximilian Gorsky (Technische Universität Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Japan); Stephan Kreutzer (Technische Universität Berlin); Sebastian Wiederrecht (Institute for Basic Science, South Korea)

Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen (Duke University); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University)

Reconfiguration of Basis Pairs in Regular Matroids
Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz (Eötvös Loránd University)

The Power of Adaptivity in Quantum Query Algorithms
Uma Girish (Princeton University); Makrand Sinha (University of Illinois at Urbana-Champaign); Avishay Tal, Kewen Wu (University of California at Berkeley)

Online Edge-Coloring is (Nearly) as Easy as Offline
Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); Ola Svensson, Radu Vintan (EPFL); David Wajc (Technion — Israel Institute of Technology)

How to Use Quantum Indistinguishability Obfuscation
Andrea Coladangelo (University of Washington); Sam Gunn (UC Berkeley)

Semigroup algorithmic problems in metabelian groups
Ruiwen Dong (University of Oxford)

Prize-Collecting Steiner Tree: A 1.79 Approximation
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi (University of Maryland)

Supermodular Approximation of Norms and Applications
Thomas Kesselheim (University of Bonn); Marco Molinaro (PUC-Rio); Sahil Singla (Georgia Tech)

Optimal Load-Balanced Scalable Distributed Agreement
Yuval Gelles (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research)

Trickle-Down in Localization Schemes and Applications
Nima Anari, Frederic Koehler, Thuy-Duong Vuong (Stanford University)

Sampling Balanced Forests of Grids in Polynomial Time
Sarah Cannon (Claremont McKenna College); Wesley Pegden (Carnegie Mellon University); Jamie Tucker-Foltz (Harvard University)

XOR Lemmas for Communication via Marginal Information
Siddharth Iyer (University of Washington); Anup Rao (School of Computer Science, University of Washington)

Complexity-Theoretic Implications of Multicalibration
Sílvia Casacuberta (University of Oxford); Cynthia Dwork, Salil Vadhan (Harvard University)

Random (log n)-CNF are Hard for Cutting Planes (Again)
Dmitry Sokolov (EPFL)

Classical simulation of peaked shallow quantum circuits
Sergey Bravyi (IBM Quantum, T. J. Watson Research Center); David Gosset, Yinchen Liu (University of Waterloo)

The Power of Two-sided Recruitment in Two-sided Markets
Yang Cai (Yale University); Christopher Liaw, Aranyak Mehta (Google); Mingfei Zhao (Google Research)

Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research)

Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, Mark Rudelson (University of Michigan)

(1 − ε)-Approximation of Knapsack in Nearly Quadratic Time
Xiao Mao (Stanford University)

Local Correction of Linear Functions over the Boolean Cube
Prashanth Amireddy (Harvard University); Amik Raj Behera (Aarhus University); Manaswi Paraashar, Srikanth Srinivasan (University of Copenhagen); Madhu Sudan (Harvard University)

Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams
Sepehr Assadi (University of Waterloo and Rutgers University); Gillat Kol, Zhijun Zhang (Princeton University)

Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer (University of Texas at Austin); William Kretschmer (Simons Institute); Daniel Liang (Rice University)

A Flat Wall Theorem for Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece); Sebastian Wiederrecht (Discrete Mathematics Group, IBS, Daejeon, South Korea)

Strong Algebras and Radical Sylvester-Gallai Configurations
Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo)

Revisiting Local Computation of PageRank: Simple and Optimal
Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang (Renmin University of China)

Solving Dense Linear Systems Faster than via Preconditioning
Michal Derezinski, Jiaming Yang (University of Michigan)

Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen (University of California at Berkeley); Shuichi Hirahara (National Institute of Informatics); Hanlin Ren (University of Oxford)

Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta (BARC, University of Copenhagen); Aviad Rubinstein (Stanford University)

Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University)

Strategic Budget Selection in a Competitive Autobidding World
Yiding Feng (University of Chicago); Brendan Lucier, Aleksandrs Slivkins (Microsoft Research)

Constant Query Local Decoding Against Deletions is Impossible
Meghal Gupta (UC Berkeley)

Minimum Star Partitions of Simple Polygons in Polynomial Time
Mikkel Abrahamsen (University of Copenhagen); Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); André Nusser, Hanwen Zhang (University of Copenhagen)

No Complete Problem for Constant-Cost Randomized Communication
Yuting Fang (The Ohio State University); Lianna Hambardzumyan (The Hebrew University of Jerusalem); Nathaniel Harms (EPFL); Pooya Hatami (The Ohio State University)

Polylog-Competitive Deterministic Local Routing and Scheduling
Bernhard Haeupler (ETH Zurich & CMU); Shyamal Patel (Columbia University); Antti Roeyskoe (ETH Zurich); Cliff Stein (Columbia University); Goran Zuzic (Google Research)

Local geometry of NAE-SAT solutions in the condensation regime
Allan Sly (Princeton University); Youngtak Sohn (MIT)

Characterizing Direct Product Testing via Coboundary Expansion
Mitali Bafna, Dor Minzer (MIT)

Counting Small Induced Subgraphs with Edge-monotone Properties
Simon Döring (Max Planck Institute for Informatics; Saarbrücken Graduate School of Computer Science; Saarland Informatics Campus); Dániel Marx (CISPA Helmholtz Center for Information Security); Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus)

Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Tegan Wilson, Daniel Amir, Nitika Saran, Robert Kleinberg (Cornell University); Vishal Shrivastav (Purdue University); Hakim Weatherspoon (Cornell University)

Prophet Inequalities Require Only a Constant Number of Samples
Andres Cristi (Universidad de Chile); Bruno Ziliotto (CNRS)

On Optimal Coreset Construction for Euclidean (k,z)-clustering
Lingxiao Huang (Nanjing University); Jian Li, Xuan Wu (Tsinghua University)

No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy (School of Computation, Information and Technology, Technical University of Munich, Munich Center for Quantum Science and Technology); Francesco d'Amore (Aalto University and Bocconi University); Rishikesh Gajjala (Indian Institute of Science and Aalto University); Fabian Kuhn (University of Freiburg); François Le Gall (Nagoya University); Henrik Lievonen, Augusto Modanese (Aalto University); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau); Gustav Schmid (University of Freiburg); Jukka Suomela (Aalto University)

Circuit-to-Hamiltonian from tensor networks and fault tolerance
Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Quynh T Nguyen (Harvard University)

On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka (Max Planck Institute for Informatics, SIC); Jakob Nogler (ETH Zurich); Philip Wellnitz (Max Planck Institute for Informatics, SIC)

The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley (University of Liverpool); Paul W. Goldberg, Alexandros Hollender (University of Oxford); Rahul Savani (University of Liverpool)

Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors
Yulin Wang, Chihao Zhang (Shanghai Jiao Tong University); Zihan Zhang (Graduate Institute for Advanced Studies, SOKENDAI)

Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka (Weizmann Institute of Science); Seth Pettie (University of Michigan)

No-Regret Learning in Bilateral Trade via Global Budget Balance
Martino Bernasconi (Bocconi University); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Federico Fusco (Sapienza University of Rome)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli, Shyamal Patel (Columbia University)

Combinatorial Characterizations of Monadically NIP Graph Classes
Jan Dreier (TU Wien); Nikolas Mählmann (University of Bremen); Szymon Torunczyk (University of Warsaw)

An efficient quantum parallel repetition theorem and applications
John Bostanci (Columbia University); Luowen Qian (Boston University); Nick Spooner (University of Warwick & NYU); Henry Yuen (Columbia University)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

Testing Closeness of Multivariate Distributions via Ramsey Theory
Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane, Sihan Liu (University of California, San Diego)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University)

Orthogonal arrays and universal hashing with arbitrary parameters
Nicholas Harvey, Arvin Sahami (UBC)

Quantum and classical query complexities of functions of matrices
Ashley Montanaro (University of Bristol); Changpeng Shao (Academy of Mathematics and Systems Science, Chinese Academy of Sciences)

Proof of the density threshold conjecture for pinwheel scheduling
Akitoshi Kawamura (Kyoto University)

AG codes achieve list decoding capacity over constant-sized fields
Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research); Zihan Zhang (The Ohio State University)

Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval
William Kuszmaul (Harvard University); Stefan Walzer (Karlsruhe Institute of Technology)

Learning quantum Hamiltonians at any temperature in polynomial time
Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley)

Semidefinite programs simulate approximate message passing robustly
Misha Ivkov, Tselil Schramm (Stanford)

Understanding the Cluster Linear Program for Correlation Clustering
Nairen Cao (Boston College); Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (Nanjing University); Alantha Newman (CNRS-Université Grenoble Alpes); Lukas Vogl (Ecole Polytechnique Federale de Lausanne)

Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton, Gregory Valiant (Stanford University)

Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie (NYU Shanghai); Yuping Ye (East China Normal University and NYU Shanghai)

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University)

Robust recovery for stochastic block models, simplified and generalized
Sidhanth Mohanty (MIT); Prasad Raghavendra, David Wu (U.C. Berkeley);

Semidefinite programming and linear equations vs. homomorphism problems
Lorenzo Ciardo, Stanislav Živný (University of Oxford)

On The Fourier Coefficients of High-Dimensional Random Geometric Graphs
Kiril Bangachev, Guy Bresler (MIT)

Single-Source Shortest Paths with Negative Real Weights in Õ(mn^8/9) Time
Jeremy T. Fineman (Georgetown University)

Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin (TTIC)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss (University of Warwick); Aaron Sidford (Stanford University); David Wajc (Technion)

Approaching the Quantum Singleton Bound with Approximate Error Correction
Thiago Bergamaschi, Louis Golowich, Sam Gunn (UC Berkeley)

O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set
Sepehr Assadi (Rutgers University and University of Waterloo); Christian Konrad, Kheeran K. Naidu (University of Bristol); Janani Sundaresan (University of Waterloo)

A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
Brent Waters (University of Texas at Austin and NTT Research)

Maximum Bipartite Matching in n^2+o(1) Time via a Combinatorial Algorithm
Julia Chuzhoy (Toyota Technological Institute at Chicago); Sanjeev Khanna (University of Pennsylvania)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London)

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Venkatesan Guruswami (University of California, Berkeley); Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Kewen Wu (University of California, Berkeley)

Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Xiao Mao (Stanford University)

Limitations of Stochastic Selection Problems with Pairwise Independent Priors
Shaddin Dughmi, Yusuf Kalayci, Neel Patel (University of Southern California)

The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
Andreas Björklund (IT University of Copenhagen); Petteri Kaski (Aalto University)

Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
Pravesh Kothari (CMU); Aaron Potechin (University of Chicago); Jeff Xu (CMU)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
Tuukka Korhonen (University of Bergen); Marek Sokolowski (University of Warsaw)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Xi Chen (Columbia University); Yumou Fei (Peking University); Shyamal Patel (Columbia University)

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais, Cameron Seth (University of Waterloo)

A one-query lower bound for unitary synthesis and breaking quantum cryptography
Alex Lombardi (Princeton); Fermi Ma (Simons Institute and UC Berkeley); John Wright (UC Berkeley)

A New Information Complexity Measure for Multi-Pass Streaming with Applications
Mark Braverman (Princeton University); Sumegha Garg (Rutgers University); Qian Li (Shenzhen Research Institute of Big Data); Shuo Wang (Shanghai Jiao Tong University); David P. Woodruff (CMU); Jiapeng Zhang (University of Southern California)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
Benjamin Rossman (Duke University)

Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Brent Waters (University of Texas at Austin and NTT Research); David J. Wu (University of Texas at Austin)

From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
Yuval Dagan (UC Berkeley); Constantinos Daskalakis (EECS, MIT); Maxwell Fishelson (Massachusetts Institute of Technology); Noah Golowich (MIT)

Communication Lower Bounds for Collision Problems via Density Increment Arguments
Guangxu Yang, Jiapeng Zhang (University of Southern California)

An optimal tradeoff between entanglement and copy complexity for state tomography
Sitan Chen (Harvard University); Jerry Li (Microsoft Research); Allen Liu (MIT)

Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri (MIT); Yin Tat Lee (University Washington and Microsoft Research); Swati Padmanabhan (MIT); William Swartworth, David P. Woodruff (Carnegie Mellon University); Guanghao Ye (MIT)

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
Nicolo Cesa-Bianchi (University of Milan); Tommaso Cesari (University of Ottawa); Roberto Colomboni (Italian Institute of Technology & University of Milan); Federico Fusco (Sapienza); Stefano Leonardi (University of Rome La Sapienza)

The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups
Bireswar Das, Dhara Thakkar (IIT Gandhinagar)

A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
Jason Gaitonde (Massachusetts Institute of Technology); Elchanan Mossel (MIT)

A constant-factor approximation for Nash social welfare with subadditive valuations
Shahar Dobzinski (Weizmann Institute); Wenzheng Li, Aviad Rubinstein, Jan Vondrak (Stanford University)

Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng (Columbia University); Aviad Rubinstein (Stanford University)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer (Weizmann Institute of Science); Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
Saeed Mehraban (Tufts University); Mehrdad Tahmasbi (UIUC)

Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs
Thomas Debris-Alazard (Inria); Pouria Fallahpour (ENS de Lyon, France); Damien Stehlé (CryptoLab Inc, Lyon, France)

Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland (University of California at Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Tomáš Masarík, Marcin Pilipczuk, Michal Pilipczuk (University of Warsaw); Pawel Rzazewski (Warsaw University of Technology)

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
Yilei Chen (Tsinghua University and Shanghai Qi Zhi Institute); Jiatu Li (Massachusetts Institute of Technology)

Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
Hossein Esfandiari (Google); Praneeth Kacham (Carnegie Mellon University); Vahab Mirrokni (Google Research); David P. Woodruff (Carnegie Mellon University); Peilin Zhong (Google Research)

Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
Swee Hong Chan (Rutgers University); Igor Pak (UCLA)

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi (MIT)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
Zeyong Li (National University of Singapore)

A stronger connection between the asymptotic rank conjecture and the set cover conjecture
Kevin Pratt (New York University)

Explicit separations between randomized and deterministic Number-on-Forehead communication
Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA)

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin, Yinzhan Xu (MIT)

Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields
Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Ray Li (Santa Clara University)

Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
Mohsen Ghaffari, Brandon Wang (MIT)

Settling the Communication Complexity of VCG-based Mechanisms for All Approximation Guarantees
Frederick Qiu, S. Matthew Weinberg (Princeton University)

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher, Ojas Parekh (Sandia National Laboratories); Nadezhda Voronova (Boston University)

An area law for the maximally-mixed ground state in arbitrarily degenerate systems with good AGSP
Itai Arad (Centre for Quantum Technologies); Raz Firanko (Technion); Rahul Jain (National University of Singapore)

Agreement theorems for high dimensional expanders in the low acceptance regime: the role of covers
Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai Mathematical Institute, India); Abhranil Chatterjee (Indian Statistical Institute, Kolkata, India); Partha Mukhopadhyay (Chennai Mathematical Institute, India)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Shuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
Uriya A. First (University of Haifa); Tali Kaufman (Bar Ilan University)

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L that Uses Properties of BPL
Dean Doron (Ben Gurion University); Edward Pyne (MIT); Roei Tell (University of Toronto)

PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas (University of Edinburgh); Kristoffer Arnsfelt Hansen, Kasper Høgh (Aarhus University); Alexandros Hollender (University of Oxford)

A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column
Daniel Dadush, Zhuan Khye Koh (CWI Amsterdam); Bento Natura (Georgia Institute of Technology); Neil Olver, László A. Végh (London School of Economics)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Aditya Bhaskara (University of Utah); Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University)

Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions
Ronen Shaltiel (University of Haifa); Jad Silbak (Northeastern University)

Learning the coefficients: A presentable version of border complexity and applications to circuit factoring
C. S. Bhargav, Prateek Dwivedi, Nitin Saxena (Department of Computer Science & Engg., Indian Institute of Technology Kanpur)

Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane (University of California, San Diego); Vasilis Kontonis (University of Texas, Austin); Sihan Liu (University of California, San Diego); Nikos Zarifis (University of Wisconsin-Madison)

Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
Calum MacRury, Will Ma (Columbia University)

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
Li Chen (Carnegie Mellon University); Rasmus Kyng (ETH Zurich); Yang P. Liu (Institute for Advanced Study); Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich)