| 2024 | (1 - ε)-Approximation of Knapsack in Nearly Quadratic Time. Xiao Mao |
| 2024 | 0-1 Knapsack in Nearly Quadratic Time. Ce Jin |
| 2024 | A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák |
| 2024 | A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications. Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg |
| 2024 | A Flat Wall Theorem for Matching Minors in Bipartite Graphs. Archontia C. Giannopoulou, Sebastian Wiederrecht |
| 2024 | A Nearly Quadratic-Time FPTAS for Knapsack. Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang |
| 2024 | A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors. Brent Waters |
| 2024 | A New Information Complexity Measure for Multi-pass Streaming with Applications. Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang |
| 2024 | A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography. Alex Lombardi, Fermi Ma, John Wright |
| 2024 | A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture. Kevin Pratt |
| 2024 | A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column. Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh |
| 2024 | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width. Jason Gaitonde, Elchanan Mossel |
| 2024 | AG Codes Achieve List Decoding Capacity over Constant-Sized Fields. Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang |
| 2024 | Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation. Brent Waters, David J. Wu |
| 2024 | Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers. Yotam Dikstein, Irit Dinur |
| 2024 | Algorithmic Contract Design (Keynote). Michal Feldman |
| 2024 | Almost Linear Size Edit Distance Sketch. Michal Koucký, Michael E. Saks |
| 2024 | Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg |
| 2024 | Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth. Tuukka Korhonen, Marek Sokolowski |
| 2024 | An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP. Itai Arad, Raz Firanko, Rahul Jain |
| 2024 | An Efficient Quantum Parallel Repetition Theorem and Applications. John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen |
| 2024 | An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. Pravesh K. Kothari, Peter Manohar |
| 2024 | An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography. Sitan Chen, Jerry Li, Allen Liu |
| 2024 | Approaching the Quantum Singleton Bound with Approximate Error Correction. Thiago Bergamaschi, Louis Golowich, Sam Gunn |
| 2024 | Approximate Earth Mover's Distance in Truly-Subquadratic Time. Lorenzo Beretta, Aviad Rubinstein |
| 2024 | Approximating Maximum Matching Requires Almost Quadratic Time. Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2024 | Approximating Partition in Near-Linear Time. Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang |
| 2024 | Approximating Small Sparse Cuts. Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak |
| 2024 | Batch Proofs Are Statistically Hiding. Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D. Rothblum, Prashant Nalini Vasudevan |
| 2024 | Beating Brute Force for Compression Problems. Shuichi Hirahara, Rahul Ilango, R. Ryan Williams |
| 2024 | Better Coloring of 3-Colorable Graphs. Ken-ichi Kawarabayashi, Mikkel Thorup, Hirotaka Yoneda |
| 2024 | Bilateral Trade with Correlated Values. Shahar Dobzinski, Ariel Shaulker |
| 2024 | Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time. Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay |
| 2024 | Black-Box PPP Is Not Turing-Closed. Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere |
| 2024 | Breaking the VLB Barrier for Oblivious Reconfigurable Networks. Tegan Wilson, Daniel Amir, Nitika Saran, Robert Kleinberg, Vishal Shrivastav, Hakim Weatherspoon |
| 2024 | Calibrated Language Models Must Hallucinate. Adam Tauman Kalai, Santosh S. Vempala |
| 2024 | Characterizing Direct Product Testing via Coboundary Expansion. Mitali Bafna, Dor Minzer |
| 2024 | Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance. Anurag Anshu, Nikolas P. Breuckmann, Quynh T. Nguyen |
| 2024 | Classical Simulation of Peaked Shallow Quantum Circuits. Sergey Bravyi, David Gosset, Yinchen Liu |
| 2024 | Combinatorial Correlation Clustering. Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang |
| 2024 | Commitments from Quantum One-Wayness. Dakshita Khurana, Kabir Tomer |
| 2024 | Communication Lower Bounds for Collision Problems via Density Increment Arguments. Guangxu Yang, Jiapeng Zhang |
| 2024 | Complexity-Theoretic Implications of Multicalibration. Sílvia Casacuberta, Cynthia Dwork, Salil P. Vadhan |
| 2024 | Computing a Fixed Point of Contraction Maps in Polynomial Queries. Xi Chen, Yuhao Li, Mihalis Yannakakis |
| 2024 | Connectivity Labeling and Routing with Multiple Vertex Failures. Merav Parter, Asaf Petruschka, Seth Pettie |
| 2024 | Constant Query Local Decoding against Deletions Is Impossible. Meghal Gupta |
| 2024 | Constrained Submodular Maximization via New Bounds for DR-Submodular Functions. Niv Buchbinder, Moran Feldman |
| 2024 | Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes. Uriya A. First, Tali Kaufman |
| 2024 | Counting Small Induced Subgraphs with Edge-Monotone Properties. Simon Döring, Dániel Marx, Philip Wellnitz |
| 2024 | Data-Dependent LSH for the Earth Mover's Distance. Rajesh Jayaram, Erik Waingarten, Tian Zhang |
| 2024 | Detecting Low-Degree Truncation. Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio |
| 2024 | Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries. Xi Chen, Yumou Fei, Shyamal Patel |
| 2024 | Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time. Mohsen Ghaffari, Christoph Grunau |
| 2024 | Edge-Disjoint Paths in Eulerian Digraphs. Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer |
| 2024 | Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial Hierarchy. Swee Hong Chan, Igor Pak |
| 2024 | Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions. Ronen Shaltiel, Jad Silbak |
| 2024 | Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters. Nicholas Harvey, Arvin Sahami |
| 2024 | Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. Zander Kelley, Shachar Lovett, Raghu Meka |
| 2024 | Explicit Two-Sided Unique-Neighbor Expanders. Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes |
| 2024 | Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. Noah Golowich, Ankur Moitra, Dhruv Rohatgi |
| 2024 | Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. John Kallaugher, Ojas Parekh, Nadezhda Voronova |
| 2024 | Fair Division via Quantile Shares. Yakov Babichenko, Michal Feldman, Ron Holzman, Vishnu V. Narayan |
| 2024 | Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. Binghui Peng, Aviad Rubinstein |
| 2024 | Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes. Jan Dreier, Nikolas Mählmann, Szymon Torunczyk |
| 2024 | Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication. Benjamin Rossman |
| 2024 | From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces. Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich |
| 2024 | Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time. Xiao Mao |
| 2024 | Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret |
| 2024 | Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. Joshua Brakensiek, Manik Dhar, Sivakanth Gopi |
| 2024 | Ghost Value Augmentation for k-Edge-Connectivity. D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen |
| 2024 | Hardness Condensation by Restriction. Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov |
| 2024 | Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. Yilei Chen, Jiatu Li |
| 2024 | How Random CSPs Fool Hierarchies. Siu On Chan, Hiu Tsun Ng, Sijin Peng |
| 2024 | How to Use Quantum Indistinguishability Obfuscation. Andrea Coladangelo, Sam Gunn |
| 2024 | Hypergraph Unreliability in Quasi-Polynomial Time. Ruoxu Cen, Jason Li, Debmalya Panigrahi |
| 2024 | Improved Stabilizer Estimation via Bell Difference Sampling. Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang |
| 2024 | Improving the Bit Complexity of Communication for Distributed Convex Optimization. Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye |
| 2024 | Influences in Mixing Measures. Frederic Koehler, Noam Lifshitz, Dor Minzer, Elchanan Mossel |
| 2024 | Knapsack with Small Items in Near-Quadratic Time. Karl Bringmann |
| 2024 | Learning Quantum Hamiltonians at Any Temperature in Polynomial Time. Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang |
| 2024 | Learning Shallow Quantum Circuits. Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, Jarrod R. McClean |
| 2024 | Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring. C. S. Bhargav, Prateek Dwivedi, Nitin Saxena |
| 2024 | Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability. Mohsen Ghaffari, Brandon Wang |
| 2024 | Limitations of Stochastic Selection Problems with Pairwise Independent Priors. Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel |
| 2024 | Local Borsuk-Ulam, Stability, and Replicability. Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff |
| 2024 | Local Correction of Linear Functions over the Boolean Cube. Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan |
| 2024 | Local Geometry of NAE-SAT Solutions in the Condensation Regime. Allan Sly, Youngtak Sohn |
| 2024 | Local Minima in Quantum Systems. Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou |
| 2024 | Locality Bounds for Sampling Hamming Slices. Daniel M. Kane, Anthony Ostuni, Kewen Wu |
| 2024 | Low-Step Multi-commodity Flow Emulators. Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak |
| 2024 | Lower Bounds for Regular Resolution over Parities. Klim Efremenko, Michal Garlík, Dmitry Itsykson |
| 2024 | Maximum Bipartite Matching in n Julia Chuzhoy, Sanjeev Khanna |
| 2024 | Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski |
| 2024 | Memory Checking Requires Logarithmic Overhead. Elette Boyle, Ilan Komargodski, Neekon Vafa |
| 2024 | Minimum Star Partitions of Simple Polygons in Polynomial Time. Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang |
| 2024 | Near Optimal Alphabet-Soundness Tradeoff PCPs. Dor Minzer, Kai Zhe Zheng |
| 2024 | Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc |
| 2024 | Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances. Spencer Compton, Gregory Valiant |
| 2024 | Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin |
| 2024 | Nearly Optimal Fault Tolerant Distance Oracle. Dipan Dey, Manoj Gupta |
| 2024 | New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka |
| 2024 | New Graph and Hypergraph Container Lemmas with Applications in Property Testing. Eric Blais, Cameron Seth |
| 2024 | New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan |
| 2024 | No Complete Problem for Constant-Cost Randomized Communication. Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami |
| 2024 | No Distributed Quantum Advantage for Approximate Graph Coloring. Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela |
| 2024 | No-Regret Learning in Bilateral Trade via Global Budget Balance. Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco |
| 2024 | Nonlinear Dynamics for the Ising Model. Pietro Caputo, Alistair Sinclair |
| 2024 | Nonlocality under Computational Assumptions. Grzegorz Gluch, Khashayar Barooti, Alexandru Gheorghiu, Marc-Olivier Renou |
| 2024 | O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set. Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan |
| 2024 | On Approximability of Satisfiable k-CSPs: IV. Amey Bhangale, Subhash Khot, Dor Minzer |
| 2024 | On Optimal Coreset Construction for Euclidean (k, z)-Clustering. Lingxiao Huang, Jian Li, Xuan Wu |
| 2024 | On the Communication Complexity of Approximate Pattern Matching. Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz |
| 2024 | On the Fourier Coefficients of High-Dimensional Random Geometric Graphs. Kiril Bangachev, Guy Bresler |
| 2024 | On the Pauli Spectrum of QAC0. Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen |
| 2024 | On the Power of Homogeneous Algebraic Formulas. Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas |
| 2024 | On the Power of Interactive Proofs for Learning. Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar |
| 2024 | One-Way Functions and Zero Knowledge. Shuichi Hirahara, Mikito Nanashima |
| 2024 | Online Edge Coloring Is (Nearly) as Easy as Offline. Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc |
| 2024 | Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL. Dean Doron, Edward Pyne, Roei Tell |
| 2024 | Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong |
| 2024 | Optimal Embedding Dimension for Sparse Subspace Embeddings. Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, Mark Rudelson |
| 2024 | Optimal Load-Balanced Scalable Distributed Agreement. Yuval Gelles, Ilan Komargodski |
| 2024 | Optimal Multi-pass Lower Bounds for MST in Dynamic Streams. Sepehr Assadi, Gillat Kol, Zhijun Zhang |
| 2024 | Optimal Non-adaptive Tolerant Junta Testing via Local Estimators. Shivam Nadimpalli, Shyamal Patel |
| 2024 | Optimal Online Discrepancy Minimization. Janardhan Kulkarni, Victor Reis, Thomas Rothvoss |
| 2024 | Optimization with Pattern-Avoiding Input. Benjamin Aram Berendsohn, László Kozma, Michal Opler |
| 2024 | PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization. Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender |
| 2024 | Packing Even Directed Circuits Quarter-Integrally. Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, Sebastian Wiederrecht |
| 2024 | Parallel Sampling via Counting. Nima Anari, Ruiquan Gao, Aviad Rubinstein |
| 2024 | Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu |
| 2024 | Perfect Zero-Knowledge PCPs for #P. Tom Gur, Jack O'Connor, Nicholas Spooner |
| 2024 | Planted Clique Conjectures Are Equivalent. Shuichi Hirahara, Nobutaka Shimizu |
| 2024 | Polylog-Competitive Deterministic Local Routing and Scheduling. Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe, Cliff Stein, Goran Zuzic |
| 2024 | Private Graphon Estimation via Sum-of-Squares. Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer |
| 2024 | Prize-Collecting Steiner Tree: A 1.79 Approximation. Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi |
| 2024 | Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. Shuichi Hirahara, Naoto Ohsaka |
| 2024 | Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 Bojan Mohar, Igor Shinkar, Ryan O'Donnell |
| 2024 | Product Mixing in Compact Lie Groups. David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer |
| 2024 | Proof of the Density Threshold Conjecture for Pinwheel Scheduling. Akitoshi Kawamura |
| 2024 | Prophet Inequalities Require Only a Constant Number of Samples. Andrés Cristi, Bruno Ziliotto |
| 2024 | Prophet Inequalities with Cancellation Costs. Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák |
| 2024 | Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach. Saeed Mehraban, Mehrdad Tahmasbi |
| 2024 | Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs. Thomas Debris-Alazard, Pouria Fallahpour, Damien Stehlé |
| 2024 | Quantum State Obfuscation from Classical Oracles. James Bartusek, Zvika Brakerski, Vinod Vaikuntanathan |
| 2024 | Quantum Time-Space Tradeoffs for Matrix Problems. Paul Beame, Niels Kornerup, Michael Whitmeyer |
| 2024 | Quantum and Classical Query Complexities of Functions of Matrices. Ashley Montanaro, Changpeng Shao |
| 2024 | Random (log n)-CNF Are Hard for Cutting Planes (Again). Dmitry Sokolov |
| 2024 | Random-Order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals. Calum MacRury, Will Ma |
| 2024 | Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. Omar Alrabiah, Venkatesan Guruswami, Ray Li |
| 2024 | Reconfiguration of Basis Pairs in Regular Matroids. Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz |
| 2024 | Relaxed Local Correctability from Local Testing. Vinayak M. Kumar, Geoffrey Mon |
| 2024 | Revisiting Local Computation of PageRank: Simple and Optimal. Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang |
| 2024 | Robust Recovery for Stochastic Block Models, Simplified and Generalized. Sidhanth Mohanty, Prasad Raghavendra, David X. Wu |
| 2024 | SNARGs under LWE via Propositional Proofs. Zhengzhong Jin, Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan |
| 2024 | Sampling Balanced Forests of Grids in Polynomial Time. Sarah Cannon, Wesley Pegden, Jamie Tucker-Foltz |
| 2024 | Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors. Yulin Wang, Chihao Zhang, Zihan Zhang |
| 2024 | Self-Improvement for Circuit-Analysis Problems. R. Ryan Williams |
| 2024 | Semidefinite Programming and Linear Equations vs. Homomorphism Problems. Lorenzo Ciardo, Stanislav Zivný |
| 2024 | Semidefinite Programs Simulate Approximate Message Passing Robustly. Misha Ivkov, Tselil Schramm |
| 2024 | Semigroup Algorithmic Problems in Metabelian Groups. Ruiwen Dong |
| 2024 | Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees. Frederick V. Qiu, S. Matthew Weinberg |
| 2024 | Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More. Ce Jin, Yinzhan Xu |
| 2024 | Single-Source Shortest Paths with Negative Real Weights in Jeremy T. Fineman |
| 2024 | Solving Dense Linear Systems Faster Than via Preconditioning. Michal Derezinski, Jiaming Yang |
| 2024 | Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval. William Kuszmaul, Stefan Walzer |
| 2024 | Sparsifying Generalized Linear Models. Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford |
| 2024 | Strategic Budget Selection in a Competitive Autobidding World. Yiding Feng, Brendan Lucier, Aleksandrs Slivkins |
| 2024 | Strong Algebras and Radical Sylvester-Gallai Configurations. Rafael Oliveira, Akash Kumar Sengupta |
| 2024 | Structural Complexities of Matching Mechanisms. Yannai A. Gonczarowski, Clayton Thomas |
| 2024 | Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. Pravesh K. Kothari, Aaron Potechin, Jeff Xu |
| 2024 | Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs. Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis |
| 2024 | Supermodular Approximation of Norms and Applications. Thomas Kesselheim, Marco Molinaro, Sahil Singla |
| 2024 | Swap Cosystolic Expansion. Yotam Dikstein, Irit Dinur |
| 2024 | Symmetric Exponential Time Requires Near-Maximum Circuit Size. Lijie Chen, Shuichi Hirahara, Hanlin Ren |
| 2024 | Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform. Zeyong Li |
| 2024 | Testing Closeness of Multivariate Distributions via Ramsey Theory. Ilias Diakonikolas, Daniel M. Kane, Sihan Liu |
| 2024 | The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True. Andreas Björklund, Petteri Kaski |
| 2024 | The Complexity of Computing KKT Solutions of Quadratic Programs. John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani |
| 2024 | The Computer in the Sky (Keynote). Tim Roughgarden |
| 2024 | The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups. Bireswar Das, Dhara Thakkar |
| 2024 | The Power of Adaptivity in Quantum Query Algorithms. Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu |
| 2024 | The Power of Two-Sided Recruitment in Two-Sided Markets. Yang Cai, Christopher Liaw, Aranyak Mehta, Mingfei Zhao |
| 2024 | The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi |
| 2024 | Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem. Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, Yuping Ye |
| 2024 | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2024 | Tree Evaluation Is in Space O(log n · log log n). James Cook, Ian Mertz |
| 2024 | Trickle-Down in Localization Schemes and Applications. Nima Anari, Frederic Koehler, Thuy-Duong Vuong |
| 2024 | Two Prover Perfect Zero Knowledge for MIP. Kieran Mastel, William Slofstra |
| 2024 | Understanding the Cluster Linear Program for Correlation Clustering. Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl |
| 2024 | Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping. Mohsen Ghaffari, Christoph Grunau |
| 2024 | XOR Lemmas for Communication via Marginal Information. Siddharth Iyer, Anup Rao |