STOC 2024 Accepted Papers


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

  • On the Pauli Spectrum of QAC0
    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 Õ(mn8/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 n2+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)