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)