| 2025 | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, Columbia University, New York, NY, USA, January 7-10, 2025 Raghu Meka |
| 2025 | A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, Qianfan Zhang |
| 2025 | A High Dimensional Cramer's Rule Connecting Homogeneous Multilinear Equations to Hyperdeterminants. Antoine Joux, Anand Kumar Narayanan |
| 2025 | A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications. Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley |
| 2025 | A Quantum Unique Games Conjecture. Hamoon Mousavi, Taro Spirig |
| 2025 | A Universal Sequence of Tensors for the Asymptotic Rank Conjecture. Petteri Kaski, Mateusz Michalek |
| 2025 | Accumulation Without Homomorphism. Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, William Wang |
| 2025 | Adjacency Labeling Schemes for Small Classes. Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev |
| 2025 | Algorithmic Collusion Without Threats. Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, Juba Ziani |
| 2025 | Approximate Unitary k-Designs from Shallow, Low-Communication Circuits (Extended Abstract). Nicholas LaRacuente, Felix Leditzky |
| 2025 | Backdoor Defense, Learnability and Obfuscation. Paul F. Christiano, Jacob Hilton, Victor Lecomte, Mark Xu |
| 2025 | Bosonic Quantum Computational Complexity. Ulysse Chabaud, Michael Joseph, Saeed Mehraban, Arsalan Motamedi |
| 2025 | Catalytic Communication. Edward Pyne, Nathan S. Sheffield, William Wang |
| 2025 | Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions). Aadityan Ganesh, Jason D. Hartline |
| 2025 | Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic. Geri Gokaj, Marvin Künnemann |
| 2025 | Complexity Classification of Product State Problems for Local Hamiltonians. John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka |
| 2025 | Concentration of Submodular Functions and Read-k Families Under Negative Dependence. Sharmila Duppala, George Li, Juan Luque, Aravind Srinivasan, Renata Valieva |
| 2025 | Confusion Matrix Design for Downstream Decision-Making (Extended Abstract). Yiding Feng, Wei Tang |
| 2025 | Coresets for 1-Center in 𝓁₁ Metrics. Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, Robert Krauthgamer |
| 2025 | Data Reconstruction: When You See It and When You Don't. Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, Eliad Tsfadia |
| 2025 | Data-Driven Solution Portfolios. Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii |
| 2025 | Derandomized Squaring: An Analytical Insight into Its True Behavior. Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled |
| 2025 | Detecting and Correcting Computationally Bounded Errors: A Simple Construction Under Minimal Assumptions. Jad Silbak, Daniel Wichs |
| 2025 | Deterministic Approximation for the Volume of the Truncated Fractional Matching Polytope. Heng Guo, Vishvajeet N |
| 2025 | Differential Privacy and Sublinear Time Are Incompatible Sometimes. Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, Tamalika Mukherjee |
| 2025 | Differential Privacy on Trust Graphs. Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Serena Wang |
| 2025 | Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing. Deeparnab Chakrabarty, C. Seshadhri |
| 2025 | Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, Julian Werthmann |
| 2025 | Diversity in Evolutionary Dynamics (Extended Abstract). Yuval Rabani, Leonard J. Schulman, Alistair Sinclair |
| 2025 | Doubly Sub-Linear Interactive Proofs of Proximity. Noga Amir, Oded Goldreich, Guy N. Rothblum |
| 2025 | Edge-Minimum Walk of Modular Length in Polynomial Time. Antoine Amarilli, Benoît Groz, Nicole Wein |
| 2025 | Entry-Specific Matrix Estimation Under Arbitrary Sampling Patterns Through the Lens of Network Flows (Extended Abstract). Yudong Chen, Xumei Xi, Christina Lee Yu |
| 2025 | Error Correction for Message Streams. Meghal Gupta, Rachel Yun Zhang |
| 2025 | Error-Correcting Graph Codes. Swastik Kopparty, Aditya Potukuchi, Harry Sha |
| 2025 | Estimating Euclidean Distance to Linearity. Andrej Bogdanov, Lorenzo Taschin |
| 2025 | Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting. Shuai Shao, Zhuxiao Tang |
| 2025 | Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems. Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, Saket Saurabh |
| 2025 | Extracting Dual Solutions via Primal Optimizers. Yair Carmon, Arun Jambulapati, Liam O'Carroll, Aaron Sidford |
| 2025 | Facility Location on High-Dimensional Euclidean Spaces. Euiwoong Lee, Kijun Shin |
| 2025 | Fine-Grained Equivalence for Problems Related to Integer Linear Programming. Lars Rohwedder, Karol Wegrzycki |
| 2025 | Finite Matrix Multiplication Algorithms from Infinite Groups. Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans |
| 2025 | Formulations and Constructions of Remote State Preparation with Verifiability, with Applications. Jiayu Zhang |
| 2025 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2025 | Fully Characterizing Lossy Catalytic Computation. Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker |
| 2025 | Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing. Xinyu Mao, Guangxu Yang, Jiapeng Zhang |
| 2025 | Graph Reconstruction via MIS Queries. Christian Konrad, Conor O'Sullivan, Victor Traistaru |
| 2025 | Hardness of Sampling for the Anti-Ferromagnetic Ising Model on Random Graphs. Neng Huang, Will Perkins, Aaron Potechin |
| 2025 | Improved Lower Bounds for 3-Query Matching Vector Codes. Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi |
| 2025 | Incompressible Functional Encryption. Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, Aman Verma |
| 2025 | Information Design with Unknown Prior (Extended Abstract). Tao Lin, Ce Li |
| 2025 | Learning-Augmented Streaming Algorithms for Approximating MAX-CUT. Yinhao Dong, Pan Peng, Ali Vakilian |
| 2025 | List Decoding Bounds for Binary Codes with Noiseless Feedback. Meghal Gupta, Rachel Yun Zhang |
| 2025 | Listing 6-Cycles in Sparse Graphs. Virginia Vassilevska Williams, Alek Westover |
| 2025 | Locally Private Histograms in All Privacy Regimes. Clément L. Canonne, Abigail Gentle |
| 2025 | Low Sensitivity Hopsets. Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, Nicole Wein |
| 2025 | Nearest Neighbor Complexity and Boolean Circuits. Mason DiCicco, Vladimir Podolskii, Daniel Reichman |
| 2025 | New Direct Sum Tests. Alek Westover, Edward Yu, Kai Zhe Zheng |
| 2025 | New Pseudorandom Generators and Correlation Bounds Using Extractors. Vinayak M. Kumar |
| 2025 | On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement. Thiago Bergamaschi, Yunchao Liu |
| 2025 | On White-Box Learning and Public-Key Encryption. Yanyi Liu, Noam Mazor, Rafael Pass |
| 2025 | Online Balanced Allocation of Dynamic Components. Rajmohan Rajaraman, Omer Wasim |
| 2025 | Online Versus Offline Adversaries in Property Testing. Esty Kelman, Ephraim Linder, Sofya Raskhodnikova |
| 2025 | Optimal Communication Complexity of Chained Index. Janani Sundaresan |
| 2025 | Parameterized Geometric Graph Modification with Disk Scaling. Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi |
| 2025 | Partial Minimum Branching Program Size Problem Is ETH-Hard. Ludmila Glinskih, Artur Riazanov |
| 2025 | Polynomial Size, Short-Circuit Resilient Circuits for NC. Yael Tauman Kalai, Raghuvansh R. Saxena |
| 2025 | Polynomials, Divided Differences, and Codes. S. Venkitesh |
| 2025 | Provability of the Circuit Size Hierarchy and Its Consequences. Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira, Dimitrios Tsintsilidas |
| 2025 | Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation. Dorian Rudolph, Sevag Gharibian, Daniel Nagaj |
| 2025 | Quantum Advantage and Lower Bounds in Parallel Query Complexity. Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati |
| 2025 | Quantum Communication Complexity of Classical Auctions. Aviad Rubinstein, Zixin Zhou |
| 2025 | Query Complexity of Stochastic Minimum Vertex Cover. Mahsa Derakhshan, Mohammad Saneian, Zhiyang Xun |
| 2025 | Random Restrictions of Bounded Low Degree Polynomials Are Juntas. Sreejata Kishor Bhattacharya |
| 2025 | Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity. Vladimir Podolskii, Alexander Shekhovtsov |
| 2025 | Rank Lower Bounds on Non-Local Quantum Computation. Vahid R. Asadi, Eric Culf, Alex May |
| 2025 | Robust Restaking Networks. Naveen Durvasula, Tim Roughgarden |
| 2025 | Round-Vs-Resilience Tradeoffs for Binary Feedback Channels. Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang |
| 2025 | Sampling List Packings. Evan Camrud, Ewan Davies, Alex Karduna, Holden Lee |
| 2025 | Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model. Clément L. Canonne, Sayantan Sen, Joy Qiping Yang |
| 2025 | Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance. Ittai Abraham, Gilad Asharov, Anirudh Chandramouli |
| 2025 | Simple Norm Bounds for Polynomial Random Matrices via Decoupling. Madhur Tulsiani, June Wu |
| 2025 | Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography. Prabhanjan Ananth, Fatih Kaleoglu, Henry Yuen |
| 2025 | Single-Round Proofs of Quantumness from Knowledge Assumptions. Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, Tony Metger |
| 2025 | Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem. Seth Pettie, Dingyu Wang |
| 2025 | Space Complexity of Minimum Cut Problems in Single-Pass Streams. Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff |
| 2025 | Sparsity Lower Bounds for Probabilistic Polynomials. Josh Alman, Arkadev Chattopadhyay, Ryan Williams |
| 2025 | Stable Matching with Interviews. Itai Ashlagi, Jiale Chen, Mohammad Roghani, Amin Saberi |
| 2025 | Sublinear Metric Steiner Tree via Improved Bounds for Set Cover. Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian |
| 2025 | Succinct Fermion Data Structures. Joseph Carolan, Luke Schaeffer |
| 2025 | The Computational Complexity of Factored Graphs. Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye |
| 2025 | The Local Hamiltonian Problem for Quasi-Quantum States: A Toy Model for the Quantum PCP Conjecture (Extended Abstract). Itai Arad, Miklos Santha |
| 2025 | The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions. Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz |
| 2025 | The Randomness Complexity of Differential Privacy. Clément L. Canonne, Francis E. Su, Salil P. Vadhan |
| 2025 | Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes. Nicolas Resch, Chen Yuan, Yihan Zhang |
| 2025 | Toward Separating QMA from QCMA with a Classical Oracle. Mark Zhandry |
| 2025 | Toward the Impossibility of Perfect Complete Quantum PKE from OWFs. Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu |
| 2025 | Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium. T.-H. Hubert Chan, Quan Xue |
| 2025 | When to Give up on a Parallel Implementation. Nathan S. Sheffield, Alek Westover |