| 2024 | 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024 Venkatesan Guruswami |
| 2024 | A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications. Keller Blackwell, Mary Wootters |
| 2024 | A Combinatorial Approach to Robust PCA. Weihao Kong, Mingda Qiao, Rajat Sen |
| 2024 | A Computational Separation Between Quantum No-Cloning and No-Telegraphing. Barak Nehoran, Mark Zhandry |
| 2024 | A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers. Jason Milionis, Ciamac C. Moallemi, Tim Roughgarden |
| 2024 | A Qubit, a Coin, and an Advice String Walk into a Relational Problem. Scott Aaronson, Harry Buhrman, William Kretschmer |
| 2024 | A VLSI Circuit Model Accounting for Wire Delay. Ce Jin, R. Ryan Williams, Nathaniel Young |
| 2024 | Advanced Composition Theorems for Differential Obliviousness. Mingxun Zhou, Mengshi Zhao, T.-H. Hubert Chan, Elaine Shi |
| 2024 | An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio. Mayank Goswami, Riko Jacob |
| 2024 | An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets. Rafael M. Frongillo, Maneesha Papireddygari, Bo Waggoner |
| 2024 | An Improved Protocol for ExactlyN with More Than 3 Players. Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman |
| 2024 | Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights? Aaron Bernstein, Greg Bodwin, Nicole Wein |
| 2024 | Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints. Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy |
| 2024 | Classical Verification of Quantum Learning. Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke |
| 2024 | Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle. Xingjian Li, Qipeng Liu, Angelos Pelecanos, Takashi Yamakawa |
| 2024 | Collective Tree Exploration via Potential Function Method. Romain Cosson, Laurent Massoulié |
| 2024 | Color Fault-Tolerant Spanners. Asaf Petruschka, Shay Sapir, Elad Tzalik |
| 2024 | Communicating with Anecdotes (Extended Abstract). Nika Haghtalab, Nicole Immorlica, Brendan Lucier, Markus Mobius, Divyarthi Mohan |
| 2024 | Determinants vs. Algebraic Branching Programs. Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk |
| 2024 | Deterministic 3SUM-Hardness. Nick Fischer, Piotr Kaliciak, Adam Polak |
| 2024 | Differentially Private Approximate Pattern Matching. Teresa Anna Steiner |
| 2024 | Differentially Private Medians and Interior Points for Non-Pathological Data. Maryam Aliakbarpour, Rose Silver, Thomas Steinke, Jonathan R. Ullman |
| 2024 | Discreteness of Asymptotic Tensor Ranks (Extended Abstract). Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam |
| 2024 | Distribution Testing with a Confused Collector. Renato Ferreira Pinto Jr., Nathaniel Harms |
| 2024 | Distributional PAC-Learning from Nisan's Natural Proofs. Ari Karchmer |
| 2024 | Dynamic Maximal Matching in Clique Networks. Minming Li, Peter Robinson, Xianbin Zhu |
| 2024 | Electrical Flows for Polylogarithmic Competitive Oblivious Routing. Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan |
| 2024 | Equivocal Blends: Prior Independent Lower Bounds. Jason D. Hartline, Aleck C. Johnsen |
| 2024 | Exponential-Time Approximation Schemes via Compression. Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, Saket Saurabh |
| 2024 | Extractors for Polynomial Sources over 𝔽 Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani |
| 2024 | FPT Approximation for Capacitated Sum of Radii. Ragesh Jaiswal, Amit Kumar, Jatin Yadav |
| 2024 | Fraud Detection for Random Walks. Varsha Dani, Thomas P. Hayes, Seth Pettie, Jared Saia |
| 2024 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2024 | General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. Aleksandar Nikolov, Haohua Tang |
| 2024 | Geometric Covering via Extraction Theorem. Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, Kasturi R. Varadarajan |
| 2024 | Graph Threading. Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin |
| 2024 | Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. Euiwoong Lee, Pasin Manurangsi |
| 2024 | Homogeneous Algebraic Complexity Theory and Algebraic Formulas. Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov |
| 2024 | Homomorphic Indistinguishability Obfuscation and Its Applications. Kaartik Bhushan, Venkata Koppula, Manoj Prabhakaran |
| 2024 | Influence Maximization in Ising Models. Zongchen Chen, Elchanan Mossel |
| 2024 | Intersection Classes in TFNP and Proof Complexity. Yuhao Li, William Pires, Robert Robere |
| 2024 | Kernelization of Counting Problems. Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi |
| 2024 | Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha |
| 2024 | Loss Minimization Yields Multicalibration for Large Neural Networks. Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran |
| 2024 | Lower Bounds for Planar Arithmetic Circuits. C. Ramya, Pratik Shastri |
| 2024 | Making Progress Based on False Discoveries. Roi Livni |
| 2024 | Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. Gregory Valiant |
| 2024 | Maximizing Miner Revenue in Transaction Fee Mechanism Design. Ke Wu, Elaine Shi, Hao Chung |
| 2024 | Modularity and Graph Expansion. Baptiste Louf, Colin McDiarmid, Fiona Skerman |
| 2024 | NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. Louis Golowich, Tali Kaufman |
| 2024 | Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang |
| 2024 | New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification. Prantar Ghosh, Vihan Shah |
| 2024 | Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann |
| 2024 | On Generalized Corners and Matrix Multiplication. Kevin Pratt |
| 2024 | On Parallel Repetition of PCPs. Alessandro Chiesa, Ziyi Guan, Burcu Yildiz |
| 2024 | On the (In)approximability of Combinatorial Contracts. Tomer Ezra, Michal Feldman, Maya Schlesinger |
| 2024 | On the Black-Box Complexity of Correlation Intractability. Nico Döttling, Tamer Mour |
| 2024 | On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. Monika Henzinger, Barna Saha, Martin P. Seybold, Christopher Ye |
| 2024 | On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games. Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, Manolis Zampetakis |
| 2024 | On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang |
| 2024 | On the Size Overhead of Pairwise Spanners. Ofer Neiman, Idan Shabat |
| 2024 | One-Way Functions vs. TFNP: Simpler and Improved. Lukás Folwarczný, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan |
| 2024 | Parity vs. AC0 with Simple Quantum Preprocessing. Joseph Slote |
| 2024 | Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine. Clément L. Canonne, Yucheng Sun |
| 2024 | Property Testing with Online Adversaries. Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova |
| 2024 | Proving Unsatisfiability with Hitting Formulas. Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals |
| 2024 | Pseudorandom Linear Codes Are List-Decodable to Capacity. Aaron (Louie) Putterman, Edward Pyne |
| 2024 | Pseudorandom Strings from Pseudorandom Quantum States. Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen |
| 2024 | Quantum Event Learning and Gentle Random Measurements. Adam Bene Watts, John Bostanci |
| 2024 | Quantum Merlin-Arthur and Proofs Without Relative Phase. Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha |
| 2024 | Quantum Money from Abelian Group Actions. Mark Zhandry |
| 2024 | Quantum Pseudoentanglement. Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou |
| 2024 | Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality. Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang |
| 2024 | Quickly Determining Who Won an Election. Lisa Hellerstein, Naifeng Liu, Kevin Schewior |
| 2024 | Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. Huacheng Yu, Wei Zhan |
| 2024 | Recursive Error Reduction for Regular Branching Programs. Eshan Chattopadhyay, Jyun-Jie Liao |
| 2024 | Rethinking Fairness for Human-AI Collaboration (Extended Abstract). Haosen Ge, Hamsa Bastani, Osbert Bastani |
| 2024 | Rumors with Changing Credibility. Charlotte Out, Nicolás Rivera, Thomas Sauerwald, John Sylvester |
| 2024 | Sampling, Flowers and Communication. Huacheng Yu, Wei Zhan |
| 2024 | Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election. Rex Fernando, Yuval Gelles, Ilan Komargodski |
| 2024 | Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids. Atanas Dinev, S. Matthew Weinberg |
| 2024 | Small Sunflowers and the Structure of Slice Rank Decompositions. Thomas Karam |
| 2024 | Smooth Nash Equilibria: Algorithms and Complexity. Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty |
| 2024 | Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. Justin Y. Chen, Piotr Indyk, David P. Woodruff |
| 2024 | Spanning Adjacency Oracles in Sublinear Time. Greg Bodwin, Henry L. Fleischmann |
| 2024 | Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. Iddo Tzameret, Luming Zhang |
| 2024 | Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations. Siddharth Barman, Anand Krishna, Pooja Kulkarni, Shivika Narang |
| 2024 | TFNP Intersections Through the Lens of Feasible Disjunction. Pavel Hubácek, Erfan Khaniki, Neil Thapen |
| 2024 | Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang |
| 2024 | Tensor Reconstruction Beyond Constant Rank. Shir Peleg, Amir Shpilka, Ben Lee Volk |
| 2024 | Testing Intersecting and Union-Closed Families. Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio |
| 2024 | Testing and Learning Convex Sets in the Ternary Hypercube. Hadley Black, Eric Blais, Nathaniel Harms |
| 2024 | The Chromatic Number of Kneser Hypergraphs via Consensus Division. Ishay Haviv |
| 2024 | The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees. Yi-Jun Chang |
| 2024 | The Message Complexity of Distributed Graph Optimization. Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Peter Robinson |
| 2024 | The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen |
| 2024 | The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False. Noam Mazor, Rafael Pass |
| 2024 | The Space-Time Cost of Purifying Quantum Computations. Mark Zhandry |
| 2024 | Time- and Communication-Efficient Overlay Network Construction via Gossip. Fabien Dufoulon, Michael Moorman, William K. Moses Jr., Gopal Pandurangan |
| 2024 | Total NP Search Problems with Abundant Solutions. Jiawei Li |
| 2024 | Towards Stronger Depth Lower Bounds. Gabriel Bathie, R. Ryan Williams |
| 2024 | Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. Zhao Song, Lichen Zhang, Ruizhe Zhang |
| 2024 | Two-State Spin Systems with Negative Interactions. Yumou Fei, Leslie Ann Goldberg, Pinyan Lu |
| 2024 | Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff |
| 2024 | Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round. Avrim Blum, Melissa Dutz |