ITCS - Innovations in Theoretical Computer Science
ITCS 2025 Accepted Papers
Quantum Communication Complexity of Classical Auctions Aviad Rubinstein, Zixin Zhou (Stanford University)
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing Xinyu Mao (University of Southern California); Guangxu Yang (University of Southern Califorlia); Jiapeng Zhang (University of Southern California)
Detecting and Correcting Computationally Bounded Errors: A Simple Construction Under Minimal Assumptions Jad Silbak, Daniel Wichs (Northeastern University)
Toward Separating QMA from QCMA with a Classical oracle Mark Zhandry (NTT Research)
The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions Huck Bennett (University of Colorado Boulder); Surendra Ghentiyala, Noah Stephens-Davidowitz (Cornell University)
Listing 6-Cycles in Sparse Graphs Alek Westover, Virginia Vassilevska Williams (MIT)
The Randomness Complexity of Differential Privacy Clement Canonne (University of Sydney); Francis E. Su (Harvey Mudd College); Salil P. Vadhan (Harvard University)
Backdoor defense, learnability and obfuscation Paul Christiano (unaffiliated); Jacob Hilton, Victor Lecomte, Mark Xu (Alignment Research Center)
Rank Lower Bounds on Non-local Quantum Computation Vahid R. Asadi, Eric Culf (University of Waterloo); Alex May (Perimeter Institute for Theoretical Physics)
When to Give Up on a Parallel Implementation Alek Westover, Nathan S. Sheffield (MIT)
Toward the Impossibility of Perfect Complete Quantum PKE from OWFs Longcheng Li (Institute of Computing Technology, Chinese Academy of Sciences); Qian Li (Shenzhen Research Institute of Big Data); Xingjian Li (Tsinghua University); Qipeng Liu (University of California San Diego)
Concentration of Submodular Functions and Read-k Families Under Negative Dependence Sharmila Venkata Sathya Duppala (University of Maryland, College Park); George Li (Carnegie Mellon University); Juan David Luque Chang, Aravind Srinivasan (University of Maryland, College Park, USA); Renata Valieva (University of Maryland)
Error-Correcting Graph Codes Swastik Kopparty (University of Toronto); Aditya Potukuchi (York University); Harry Sha (University of Toronto)
Random Restrictions of Bounded Low Degree Polynomials Are Juntas Sreejata Kishor Bhattacharya (Tata Institute of Fundamental Research)
Finite matrix multiplication algorithms from infinite groups Jonah Blasiak (Department of Mathematics, Drexel University); Henry Cohn (Microsoft Research and MIT Dept. of Mathematics); Joshua A. Grochow (Departments of Computer Science and Mathematics, University of Colorado Boulder, Boulder, CO 80309-0430, United States); Kevin Pratt (Courant Institute Department of Computer Science, New York University); Chris Umans (Caltech)
Fine-Grained Equivalence for Problems Related to Integer Linear Programming Lars Rohwedder (Mastricht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)
Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium T-H. Hubert Chan, Quan Xue (University of Hong Kong)
A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions Noga Alon (Princeton University); Nick Gravin (Shanghai University of Finance and Economics); Tristan Pollner, Aviad Rubinstein (Stanford University); Hongao Wang (Purdue University); S. Matthew Weinberg, Qianfan Zhang (Princeton University)
Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity Alexander Shekhovtsov (Moscow Institute of Physics and Technology); Vladimir Podolskii (Tufts University)
New Direct Sum Tests Alek Westover, Kai Zhe Zheng, Edward Yu (MIT)
Settling the complexity of testing grainedness of distributions, and application to uniformity testing in the Huge Object model Clément Canonne (University of Sydney); Sayantan Sen (National University of Singapore); Joy Qiping Yang (University of Sydney)
Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing Deeparnab Chakrabarty (Dartmouth); C. Seshadhri (University of California, Santa Cruz)
Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes Nicolas Resch (University of Amsterdam); Chen Yuan (Shanghai Jiao Tong University); Yihan Zhang (Institute of Science and Technology Austria)
Partial Minimum Branching Program Size Problem is ETH-hard Ludmila Glinskih (Google); Artur Riazanov (EPFL)
Nearest Neighbor Complexity and Boolean Circuits Daniel Reichman (Worcester Polytechnic Institute); Mason DiCicco (Worcester Polytechinc Institute); Vladimir Podolskii (Tufts University)
Algorithmic Collusion Without Threats Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth (University of Pennsylvania); Juba Ziani (Georgia Institute of Technology)
Locally Private Histograms in All Privacy Regimes Abigail Gentle (The University of Sydney); Clement Canonne (University of Sydney)
Differential Privacy on Trust Graphs Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Serena Wang (Google)
Catalytic Communication Nathan S. Sheffield, Edward Pyne, William Wang (MIT)
Space Complexity of Minimum Cut Problems in Single-Pass Streams Matthew Ding (UC Berkeley); Alexandro Garces (MIT); Jason Li, Honghao Lin (CMU); Jelani Nelson (UC Berkeley); Vihan Shah (University of Waterloo); David P. Woodruff (CMU)
Deterministic approximation for the volume of the truncated fractional matching polytope Heng Guo, Vishvajeet N (University of Edinburgh)
Data Reconstruction: When You See It and When You Don't Edith Cohen (Google and Tel Aviv University); Haim Kaplan, Yishay Mansour (Tel Aviv University and Google); Shay Moran (Technion and Google); Kobbi Nissim (Georgetown University); Uri Stemmer (Tel Aviv University and Google); Eliad Tsfadia (Georgetown University)
Data-Driven Solution Portfolios Marina Drygala (EPFL); Silvio Lattanzi (Google); Andreas Maggiori (Columbia University); Miltiadis Stouras, Ola Svensson (EPFL); Sergei Vassilvitskii (Google Research, USA)
Approximate Unitary k-Designs from Shallow, Low-Communication Circuits Nicholas LaRacuente (Indiana University Bloomington); Felix Leditzky (University of Illinois Urbana-Champaign)
Provability of the Circuit Size Hierarchy and Its Consequences Marco Carmosino (IBM Research); Valentine Kabanets (Simon Fraser University); Antonina Kolokolova (Memorial University of Newfoundland); Igor Oliveira, Dimitrios Tsintsilidas (University of Warwick)
Query Complexity of Stochastic Minimum Vertex Cover Mahsa Derakhshan, Mohammad Saneian (Northeastern University)
The Local Hamiltonian problem for quasi-quantum states: A toy model for the quantum PCP conjecture Itai Arad (Centre for Quantum Technologies); Miklos Santha (IRIF, Université de Paris; Centre for Quantum Technologies and Majulab, National University of Singapore)
Characterizing Lossy Catalytic Computation Marten Joran Folkertsma (Qusoft, CWI); Ian Mertz (University of Warwick); Florian Speelman (QuSoft, University of Amsterdam); Quinten Tupker (CWI)
Robust Restaking Networks Naveen Durvasula, Tim Roughgarden (Columbia University)
Diversity in Evolutionary Dynamics Yuval Rabani (Hebrew University); Leonard Schulman (Caltech); Alistair Sinclair (University of California Berkeley)
Single-Round Proofs of Quantumness from Knowledge Assumptions Petia Arabadjieva (ETH Zurich); Alexandru Gheorghiu (Chalmers University and IBM Research); Victor Gitton, Tony Metger (ETH Zurich)
Parameterized Geometric Graph Modification with Disk Scaling Fedor V. Fomin, Petr A. Golovach (University of Bergen); Tanmay Inamdar (Indian Institute of Technology Jodhpur); Saket Saurabh (IMSc); Meirav Zehavi (Ben-Gurion University of the Negev)
Succinct Fermion Data Structures Joseph Carolan (University of Maryland, College Park); Luke Schaeffer (University of Waterloo)
Adjacency Labeling Schemes for Small Classes Édouard Bonnet (CNRS, ENS Lyon); Julien Duron (ENS Lyon); John Sylvester, Viktor Zamaraev (University of Liverpool)
Doubly Sub-linear Interactive Proofs of Proximity Guy Rothblum (Apple); Noga Amir, Oded Goldriech (Weizmann)
Coresets for 1-Center in \\ell\_1 Metrics Amir Carmel (Weizmann Institute of Science); Chengzhi Guo, Shaofeng H.-C. Jiang (Peking University); Robert Krauthgamer (Weizmann Institute of Science)
Confusion Matrix Design for Downstream Decision-making Yiding Feng (Hong Kong University of Science and Technology); Wei Tang (Chinese University of Hong Kong)
Online versus Offline Adversaries in Property Testing Esty Kelman (MIT, Boston University); Ephraim Linder, Sofya Raskhodnikova (Boston University)
Information Design with Unknown Prior Tao Lin (Harvard University); Ce Li (Boston University)
Quantum 2-SAT on low dimensional systems is QMA_1-complete: Direct embeddings and black-box simulation Dorian Rudolph, Sevag Gharibian (Paderborn University); Daniel Nagaj (Slovak Academy of Sciences)
Optimal Communication Complexity of Chained Index Janani Sundaresan (University of Waterloo)
Low Sensitivity Hopsets Chengyuan Deng, Vikrant Ashvinkumar, Aaron Bernstein, Jie Gao (Rutgers University); Nicole Wein (University of Michigan, Ann Arbor, USA)
White-Box Learning of Computationally Shallow Instances Characterizes Public-Key Encryption Yanyi Liu (Cornell Tech); Noam Mazor (Tel Aviv University); Rafael Pass (Tel Aviv University & Cornell Tech)
Completeness Theorems for k-SUM and Geometric Friends: Deciding fragments of Linear Integer Arithmetic Geri Gokaj, Marvin Künnemann (Karlsruhe Institute of Technology)
A universal sequence of tensors for the asymptotic rank conjecture Petteri Kaski (Aalto University); Mateusz Michałek (Universität Konstanz)
List Decoding Bounds for Binary Codes with Noiseless Feedback Rachel Yun Zhang (MIT); Meghal Gupta (UC Berkeley)
Graph Reconstruction via MIS Queries Christian Konrad, Conor O'Sullivan, Victor Traistaru (University of Bristol)
Sparsity Lower Bounds for Probabilistic Polynomials Josh Alman (Columbia University); Arkadev Chattopadhyay (TIFR, Mumbai); Ryan Williams (MIT)
Eulerian orientations and Hadamard codes: A novel connection via counting Shuai Shao, Zhuxiao Tang (University of Science and Technology of China)
Improved Lower Bounds for 3-Query Matching Vector Codes Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski (National University of Singapore); Sidhant Saraogi (Georgetown University)
Complexity Classification of Product State Problems for Local Hamiltonians John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang (Sandia National Labs); Justin Yirka (The University of Texas at Austin)
Combinatorial Pen Testing (or Consumer Surplus of Deferred-Acceptance Auctions) Aadityan Ganesh (Princeton University); Jason Hartline (Northwestern University)
Facility Location on High-dimensional Euclidean Spaces Euiwoong Lee (University of Michigan); Kijun Shin (Seoul National University)
A Quantum Unique Games Conjecture Hamoon Mousavi (Simons Institute for Theoretical Computer Science, University of California at Berkeley); Taro Spirig (University of Copenhagen)
Sampling List Packings Evan Camrud (Middlebury College); Ewan Davies, Alex Karduna (Colorado State University); Holden Lee (Johns Hopkins University)
Estimating Euclidean distance to linearity Andrej Bogdanov (University of Ottawa); Lorenzo Taschin (École polytechnique fédérale de Lausanne)
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT Yinhao Dong, Pan Peng (University of Science and Technology of China); Ali Vakilian (Toyota Technological Institute at Chicago)
Polynomials, Divided Differences, and Codes S. Venkitesh (University of Haifa)
Accumulation without Homomorphism Benedikt Bünz (New York University); Pratyush Mishra (University of Pennsylvania); Wilson D. Nguyen (Stanford University); William Wang (New York University)
Simple is COOL: Graded Dispersal and its Applications for Byzantine Fault Tolerance Ittai Abraham (Intel); Gilad Asharov, Anirudh Chandramouli (Bar-Ilan University)
The Computational Complexity of Factored Graphs Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye (University of California, San Diego)
Formulations and Constructions of Remote State Preparation with Verifiability, with Applications Jiayu Zhang (Zhongguancun Laboratory)
New Pseudorandom Generators and Correlation Bounds using Extractors Vinayak Kumar (UT Austin)
Simple Norm Bounds for Polynomial Random Matrices via Decoupling Madhur Tulsiani (Toyota Technological Institute at Chicago, USA); June Wu (University of Chicago)
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems Matthias Bentert, Fedor V. Fomin (University of Bergen); Tanmay Inamdar (Indian Institute of Technology Jodhpur); Saket Saurabh (IMSc)
Edge-Minimum Walk of Modular Length in Polynomial Time Antoine Amarilli (Inria Lille); Benoit Groz (Université Paris Saclay); Nicole Wein (University of Michigan)
Incompressible Functional Encryption Rishab Goyal (UW-Madison); Venkata Koppula, Mahesh Sreekumar Rajasree, Aman Verma (Indian Institute of Technology, Delhi)
Hardness of sampling for the anti-ferromagnetic Ising model on random graphs Neng Huang (University of Michigan); Will Perkins (Georgia Tech); Aaron Potechin (University of Chicago)
A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications Tsun-Ming Cheung, Hamed Hatami (School of Computer Science, McGill University); Kaave Hosseini (Department of Computer Science, University of Rochester); Aleksandar Nikolov (Department of Computer Science, University of Toronto); Toniann Pitassi (Department of Computer Science, Columbia University); Morgan Shirley (Department of Computer Science, University of Toronto)
Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography Prabhanjan Ananth, Fatih Kaleoglu (UCSB); Henry Yuen (Columbia University)
Separations and lower bounds in parallel query complexity Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati (University of Maryland, College Park)
Online Balanced Allocation of Dynamic Components Rajmohan Rajaraman, Omer Wasim (Northeastern University, USA)
Sketching, Moment Estimation, and the L'evy-Khintchine Representation Theorem Dingyu Wang, Seth Pettie (University of Michigan)
Stable Matching with Interviews Itai Ashlagi, Jiale Chen, Mohammad Roghani, Amin Saberi (Stanford University)
On fault tolerant single-shot logical state preparation and robust long-range entanglement Thiago Bergamaschi (UC Berkeley); Yunchao Liu (Harvard University)
Distributed And Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs Thorsten Götte (Universität Hamburg); Jinfeng Dou, Henning Hillebrandt, Christian Scheideler (Paderborn University); Julian Werthmann (Paderborn University, Germany)
Polynomial Size, Short-Circuit Resilient Circuits for NC Yael Tauman Kalai (Microsoft Research and MIT); Raghuvansh R. Saxena (Tata Institute of Fundamental Research)
Differential privacy and Sublinear time are incompatible sometimes Jeremiah Blocki (Purdue University); Hendrik Fichtenberger (Google Research); Elena Grigorescu (Purdue University); Tamalika Mukherjee (Columbia University)
Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows Yudong Chen (University of Wisconsin-Madison); Xumei Xi, Christina Yu (Cornell University)
Derandomized Squaring: An Analytical Insight into Its True Behavior Gal Maor, Gil Cohen, Itay Cohen (Tel Aviv University); Yuval Peled (Hebrew University)
Randomly Punctured Polynomial Ideal Codes are List Decodable with Optimal List Size Noga Ron-Zewi, S. Venkitesh (University of Haifa); Mary Wootters (Stanford University, USA)
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover Sepideh Mahabadi (Microsoft Research); Mohammad Roghani (Stanford University); Jakub Tarnawski (Microsoft Research); Ali Vakilian (Toyota Technological Institute at Chicago)
A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants Antoine Joux (CISPA – Helmholtz Center for Information Security); Anand Kumar (Sandbox AQ)
Round-vs-Resilience Tradeoffs for Binary Feedback Channels Mark Braverman (Princeton University); Klim Efremenko (Ben-Gurion University); Gillat Kol (Princeton University); Raghuvansh Saxena (Tata Institute of Fundamental Research); Zhijun Zhang (Princeton University)
