STOC 2024 Videos
| Session | Talk |
|---|---|
| 1A | Single-Source Shortest Paths with Negative Real Weights in Õ(mn⁸ᐟ⁹) Time Jeremy T. Fineman (Georgetown University) |
| Near Optimal Alphabet-Soundness Tradeoff PCPs Dor Minzer, Kai Zhe Zheng (MIT) | |
| 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) | |
| 2A | 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) |
| Approximate Earth Mover's Distance in Truly-Subquadratic Time Lorenzo Beretta (BARC, University of Copenhagen); Aviad Rubinstein (Stanford University) | |
| Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs Sayan Bhattacharya, Peter Kiss (University of Warwick); Aaron Sidford (Stanford University); David Wajc (Technion) | |
| 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) | |
| 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) | |
| 2B | Strong Algebras and Radical Sylvester-Gallai Configurations Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo) |
| 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) | |
| The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups Bireswar Das, Dhara Thakkar (IIT Gandhinagar) | |
| 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) | |
| 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) | |
| 2C | 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) |
| Calibrated Language Models Must Hallucinate Adam Tauman Kalai (Microsoft Research); Santosh Vempala (Georgia Tech) | |
| 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) | |
| Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles Noah Golowich, Ankur Moitra, Dhruv Rohatgi (MIT) | |
| Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances Spencer Compton, Gregory Valiant (Stanford University) | |
| 2D | The Power of Two-sided Recruitment in Two-sided Markets Yang Cai (Yale University); Christopher Liaw, Aranyak Mehta (Google); Mingfei Zhao (Google Research) |
| Strategic Budget Selection in a Competitive Autobidding World Yiding Feng (University of Chicago); Brendan Lucier, Aleksandrs Slivkins (Microsoft Research) | |
| 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) | |
| Bilateral Trade with Correlated Values Shahar Dobzinski (Weizmann); Ariel Shaulker (Weizmann Institute) | |
| 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) | |
| 3A | Knapsack with Small Items in Near-Quadratic Time Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics) |
| 0-1 Knapsack in Nearly Quadratic Time Ce Jin (MIT) | |
| A Nearly Quadratic-Time FPTAS for Knapsack Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University) | |
| (1 − ε)-Approximation of Knapsack in Nearly Quadratic Time Xiao Mao (Stanford University) | |
| Approximating Partition in Near-Linear Time Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University) | |
| Approximating Small Sparse Cuts Aditya Anand, Euiwoong Lee (University of Michigan); Jason Li (UC Berkeley); Thatchaphol Saranurak (University of Michigan) | |
| 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) | |
| 3B | Testing Closeness of Multivariate Distributions via Ramsey Theory Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane, Sihan Liu (University of California, San Diego) |
| Semidefinite programs simulate approximate message passing robustly Misha Ivkov, Tselil Schramm (Stanford) | |
| Planted Clique Conjectures Are Equivalent Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology) | |
| Robust recovery for stochastic block models, simplified and generalized Sidhanth Mohanty (MIT); Prasad Raghavendra, David Wu (U.C. Berkeley) | |
| 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) | |
| 3C | 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) |
| A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors Brent Waters (University of Texas at Austin and NTT Research) | |
| Optimal Load-Balanced Scalable Distributed Agreement Yuval Gelles (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research) | |
| 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) | |
| 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) | |
| 3D | Approximating Maximum Matching Requires Almost Quadratic Time Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University) |
| Structural Complexities of Matching Mechanisms Yannai A. Gonczarowski (Harvard University); Clayton Thomas (Microsoft Research) | |
| A constant-factor approximation for Nash social welfare with subadditive valuations Shahar Dobzinski (Weizmann Institute); Wenzheng Li, Aviad Rubinstein, Jan Vondrak (Stanford University) | |
| Limitations of Stochastic Selection Problems with Pairwise Independent Priors Shaddin Dughmi, Yusuf Kalayci, Neel Patel (University of Southern California) | |
| Prophet Inequalities Require Only a Constant Number of Samples Andres Cristi (Universidad de Chile); Bruno Ziliotto (CNRS) | |
| 4A | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width Jason Gaitonde (Massachusetts Institute of Technology); Elchanan Mossel (MIT) |
| Nonlinear dynamics for the Ising model Pietro Caputo (Univ Rome III); Alistair Sinclair (U.C. Berkeley) | |
| 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) | |
| On The Fourier Coefficients of High-Dimensional Random Geometric Graphs Kiril Bangachev, Guy Bresler (MIT) | |
| 4B | Classical simulation of peaked shallow quantum circuits Sergey Bravyi (IBM Quantum, T. J. Watson Research Center); David Gosset, Yinchen Liu (University of Waterloo) |
| Quantum Time-Space Tradeoffs for Matrix Problems Paul Beame (University of Washington); Niels Kornerup (University of Texas at Austin); Michael Whitmeyer (University of Washington) | |
| Circuit-to-Hamiltonian from tensor networks and fault tolerance Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Quynh T Nguyen (Harvard University) | |
| 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) | |
| Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach Saeed Mehraban (Tufts University); Mehrdad Tahmasbi (UIUC) | |
| 4C | 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) |
| Communication Lower Bounds for Collision Problems via Density Increment Arguments Guangxu Yang, Jiapeng Zhang (University of Southern California) | |
| 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) | |
| XOR Lemmas for Communication via Marginal Information Siddharth Iyer (University of Washington); Anup Rao (School of Computer Science, University of Washington) | |
| Beating Brute Force for Compression Problems Shuichi Hirahara (National Institute of Informatics, Tokyo, Japan); Rahul Ilango, Ryan Williams (MIT) | |
| 4D | Optimization with pattern-avoiding input Benjamin Aram Berendsohn, László Kozma (Freie Universität Berlin); Michal Opler (Czech Technical University in Prague) |
| 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) | |
| Packing even directed circuits quarter-integrally Maximilian Gorsky (Technische Universität Berlin); Sebastian Wiederrecht (Institute for Basic Science, South Korea); Stephan Kreutzer (Technische Universität Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) | |
| Edge-Disjoint Paths in Eulerian Digraphs Dario Giuliano Cavallaro (TU Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Stephan Kreutzer (TU Berlin) | |
| 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) | |
| 5A | Generalized GM-MDS: Polynomial Codes are Higher Order MDS Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research) |
| Constant Query Local Decoding Against Deletions is Impossible Meghal Gupta (UC Berkeley) | |
| 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) | |
| An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University) | |
| Explicit two-sided unique-neighbor expanders Jun-Ting Hsieh (Carnegie Mellon University); Theo McKenzie (Stanford University); Sidhanth Mohanty (MIT); Pedro Paredes (Princeton University) | |
| 5B | Data-Dependent LSH for the Earth Mover’s Distance Rajesh Jayaram (Google Research); Erik Waingarten, Tian Zhang (University of Pennsylvania) |
| 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) | |
| Connectivity Labeling and Routing with Multiple Vertex Failures Merav Parter, Asaf Petruschka (Weizmann Institute of Science); Seth Pettie (University of Michigan) | |
| Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams Sepehr Assadi (University of Waterloo and Rutgers University); Gillat Kol, Zhijun Zhang (Princeton University) | |
| 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) | |
| 5C | A stronger connection between the asymptotic rank conjecture and the set cover conjecture Kevin Pratt (New York University) |
| Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy Swee Hong Chan (Rutgers University); Igor Pak (UCLA) | |
| Semigroup algorithmic problems in metabelian groups Ruiwen Dong (University of Oxford) | |
| 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) | |
| 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) | |
| 6A | Revisiting Local Computation of PageRank: Simple and Optimal Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang (Renmin University of China) |
| Towards Optimal Output-Sensitive Clique Listing Mina Dalirrooyfard, Surya Mathialagan, Yinzhan Xu, Virginia Vassilevska Williams (MIT) | |
| 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) | |
| Nearly Optimal Fault Tolerant Distance Oracle Dipan Dey, Manoj Gupta (IIT Gandhinagar) | |
| Almost Linear Size Edit Distance Sketch Michal Koucký (Charles University/Rutgers University); Michael Saks (Rutgers University) | |
| 6B | Commitments from Quantum One-Wayness Dakshita Khurana (University of Illinois at Urbana-Champaign); Kabir Tomer (University of Illinois Urbana-Champaign) |
| 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) | |
| Two prover perfect zero knowledge for MIP* Kieran Mastel, William Slofstra (University of Waterloo) | |
| Quantum State Obfuscation from Classical Oracles James Bartusek (UC Berkeley); Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT CSAIL) | |
| 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) | |
| 6C | Detecting Low-Degree Truncation Anindya De, Huan Li (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University) |
| Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators Shivam Nadimpalli, Shyamal Patel (Columbia University) | |
| Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries Xi Chen (Columbia University); Yumou Fei (Peking University); Shyamal Patel (Columbia University) | |
| 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) | |
| Complexity-Theoretic Implications of Multicalibration Sílvia Casacuberta (University of Oxford); Cynthia Dwork, Salil Vadhan (Harvard University) | |
| 6D | Local geometry of NAE-SAT solutions in the condensation regime Allan Sly (Princeton University); Youngtak Sohn (MIT) |
| Trickle-Down in Localization Schemes and Applications Nima Anari, Frederic Koehler, Thuy-Duong Vuong (Stanford University) | |
| Optimal Embedding Dimension for Sparse Subspace Embeddings Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, Mark Rudelson (University of Michigan) | |
| Solving Dense Linear Systems Faster than via Preconditioning Michal Derezinski, Jiaming Yang (University of Michigan) | |
| 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) | |
| 7A | Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time Xiao Mao (Stanford University) |
| Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval William Kuszmaul (Harvard University); Stefan Walzer (Karlsruhe Institute of Technology) | |
| 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) | |
| A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich) | |
| Dynamic O(arboricity) coloring in polylogarithmic worst-case time Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich) | |
| 7B | Settling the Communication Complexity of VCG-based Mechanisms for All Approximation Guarantees Frederick Qiu, S. Matthew Weinberg (Princeton University) |
| 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) | |
| 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) | |
| Fast swap regret minimization and applications to approximate correlated equilibria Binghui Peng (Columbia University); Aviad Rubinstein (Stanford 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) | |
| Prophet Inequalities with Recourse Farbod Ekbatani, Rad Niazadeh (University of Chicago Booth School of Business); Pranav Nuti, Jan Vondrak (Stanford) | |
| 7C | Explicit orthogonal arrays and universal hashing with arbitrary parameters Nicholas Harvey, Arvin Sahami (UBC) |
| Tree Evaluation is in Space O(log n · log log n) James Cook; Ian Mertz (University of Warwick) | |
| Locality Bounds for Sampling Hamming Slices Daniel M. Kane, Anthony Ostuni (UC San Diego); Kewen Wu (UC Berkeley) | |
| 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) | |
| Explicit separations between randomized and deterministic Number-on-Forehead communication Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA) | |
| 7D | 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) |
| Local minima in quantum systems Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou (California Institute of Technology) | |
| An optimal tradeoff between entanglement and copy complexity for state tomography Sitan Chen (Harvard University); Jerry Li (Microsoft Research); Allen Liu (MIT) | |
| 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) | |
| Improved Stabilizer Estimation via Bell Difference Sampling Sabee Grewal, Vishnu Iyer (University of Texas at Austin); William Kretschmer (Simons Institute); Daniel Liang (Rice University) | |
| 8A | Computing a Fixed Point of Contraction Maps in Polynomial Queries Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University) |
| Self-Improvement for Circuit-Analysis Problems Ryan Williams (MIT) | |
| Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication Benjamin Rossman (Duke University) | |
| 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) | |
| Black-Box PPP is Not Turing-Closed Noah Fleming (Memorial University of Newfoundland); Stefan Grosser (McGill); Toniann Pitassi (Columbia); Robert Robere (McGill) | |
| 8B | Product Mixing in Compact Lie Groups David Ellis (University of Bristol); Guy Kindler, Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer (MIT) |
| On Approximability of Satisfiable k-CSPs: IV Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT) | |
| 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) | |
| Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Ray Li (Santa Clara University) | |
| 8C | Learning quantum Hamiltonians at any temperature in polynomial time Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley) |
| 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) | |
| 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) | |
| On the Pauli Spectrum of QAC⁰ Shivam Nadimpalli, Natalie Parham (Columbia University); Francisca Vasconcelos (University of California, Berkeley); Henry Yuen (Columbia University) | |
| Approaching the Quantum Singleton Bound with Approximate Error Correction Thiago Bergamaschi, Louis Golowich, Sam Gunn (UC Berkeley) | |
| 8D | 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) |
| Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin (TTIC) | |
| Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth Tuukka Korhonen (University of Bergen); Marek Sokolowski (University of Warsaw) | |
| Combinatorial Characterizations of Monadically NIP Graph Classes Jan Dreier (TU Wien); Nikolas Mählmann (University of Bremen); Szymon Torunczyk (University of Warsaw) | |
| 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) | |
| 9A | Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More Ce Jin, Yinzhan Xu (MIT) |
| Relaxed Local Correctability from Local Testing Vinayak M. Kumar, Geoffrey Mon (University of Texas at Austin) | |
| 10A | On Optimal Coreset Construction for Euclidean (k,z)-clustering Lingxiao Huang (Nanjing University); Jian Li, Xuan Wu (Tsinghua University) |
| 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) | |
| 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) | |
| Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals Calum MacRury, Will Ma (Columbia University) | |
| Prize-Collecting Steiner Tree: A 1.79 Approximation Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi (University of Maryland) | |
| 10B | Reconfiguration of Basis Pairs in Regular Matroids Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz (Eötvös Loránd University) |
| 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) | |
| Sampling Balanced Forests of Grids in Polynomial Time Sarah Cannon (Claremont McKenna College); Wesley Pegden (Carnegie Mellon University); Jamie Tucker-Foltz (Harvard University) | |
| 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) | |
| Hypergraph Unreliability in Quasi-Polynomial Time Ruoxu Cen (Duke University); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University) | |
| 10C | Memory Checking Requires Logarithmic Overhead Elette Boyle (Reichman University and NTT Research); Ilan Komargodski (Hebrew University and NTT Research); Neekon Vafa (MIT) |
| Perfect Zero-Knowledge PCPs for #P Tom Gur, Jack O'Connor (University of Cambridge); Nicholas Spooner (University of Warwick/NYU) | |
| One-Way Functions and Zero Knowledge Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology) | |
| 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) | |
| SNARGs Under LWE via Propositional Proofs Zhengzhong Jin (MIT CSAIL); Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Princeton); Vinod Vaikuntanathan (MIT CSAIL) | |
| 10D | 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) |
| Local Borsuk-Ulam, Stability, and Replicability Zachary Chase, Bogdan Chornomaz, Shay Moran (Technion); Amir Yehudayoff (Technion-IIT) | |
| 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) | |
| New Graph and Hypergraph Container Lemmas with Applications in Property Testing Eric Blais, Cameron Seth (University of Waterloo) | |
| Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model John Kallaugher, Ojas Parekh (Sandia National Laboratories); Nadezhda Voronova (Boston University) | |
| 11A | Proof of the density threshold conjecture for pinwheel scheduling Akitoshi Kawamura (Kyoto University) |
| Constrained Submodular Maximization via New Bounds for DR-Submodular Functions Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa) | |
| Optimal Online Discrepancy Minimization Janardhan Kulkarni (Microsoft Research); Victor Reis (Institute for Advanced Study); Thomas Rothvoss (University of Washington) | |
| Supermodular Approximation of Norms and Applications Thomas Kesselheim (University of Bonn); Marco Molinaro (PUC-Rio); Sahil Singla (Georgia Tech) | |
| Ghost Value Augmentation for k-ECSS and k-ECSM D Ellis Hershkowitz (Brown University); Nathan Klein (Institute for Advanced Study); Rico Zenklusen (ETH Zurich) | |
| 11B | 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) |
| Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability Mohsen Ghaffari, Brandon Wang (MIT) | |
| Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich) | |
| 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 and BIDSA); 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) | |
| 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) | |
| 11C | Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs Pravesh Kothari (CMU); Aaron Potechin (University of Chicago); Jeff Xu (CMU) |
| Semidefinite programming and linear equations vs. homomorphism problems Lorenzo Ciardo, Stanislav Živný (University of Oxford) | |
| How Random CSPs Fool Hierarchies Siu On Chan, Hiu Tsun Ng (The Chinese University of Hong Kong); Sijin Peng (Tsinghua University) | |
| Swap cosystolic expansion Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science) | |
| Characterizing Direct Product Testing via Coboundary Expansion Mitali Bafna, Dor Minzer (MIT) | |
| 11D | 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) |
| Random (log n)-CNF are Hard for Cutting Planes (Again) Dmitry Sokolov (EPFL) | |
| Hardness Condensation by Restriction Mika Göös (EPFL); Ilan Newman (University of Haifa); Artur Riazanov, Dmitry Sokolov (EPFL) | |
| 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) | |
| 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) | |