LIPIcs, Volume 325
ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA
Editors: Raghu Meka
LIPIcs, Volume 176
APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference
Editors: Jarosław Byrka and Raghu Meka
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 1-1922, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@Proceedings{meka:LIPIcs.ITCS.2025, title = {{LIPIcs, Volume 325, ITCS 2025, Complete Volume}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {1--1922}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025}, URN = {urn:nbn:de:0030-drops-229037}, doi = {10.4230/LIPIcs.ITCS.2025}, annote = {Keywords: LIPIcs, Volume 325, ITCS 2025, Complete Volume} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{meka:LIPIcs.ITCS.2025.0, author = {Meka, Raghu}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {0:i--0:xxii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.0}, URN = {urn:nbn:de:0030-drops-229028}, doi = {10.4230/LIPIcs.ITCS.2025.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Ittai Abraham, Gilad Asharov, and Anirudh Chandramouli. Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{abraham_et_al:LIPIcs.ITCS.2025.1, author = {Abraham, Ittai and Asharov, Gilad and Chandramouli, Anirudh}, title = {{Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {1:1--1:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.1}, URN = {urn:nbn:de:0030-drops-226295}, doi = {10.4230/LIPIcs.ITCS.2025.1}, annote = {Keywords: Byzantine Agreement, Broadcast} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, and Sidhant Saraogi. Improved Lower Bounds for 3-Query Matching Vector Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{aggarwal_et_al:LIPIcs.ITCS.2025.2, author = {Aggarwal, Divesh and Dutta, Pranjal and Li, Zeyong and Obremski, Maciej and Saraogi, Sidhant}, title = {{Improved Lower Bounds for 3-Query Matching Vector Codes}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {2:1--2:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.2}, URN = {urn:nbn:de:0030-drops-226308}, doi = {10.4230/LIPIcs.ITCS.2025.2}, annote = {Keywords: Locally Decodable Codes, Matching Vector Families} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Josh Alman, Arkadev Chattopadhyay, and Ryan Williams. Sparsity Lower Bounds for Probabilistic Polynomials. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{alman_et_al:LIPIcs.ITCS.2025.3, author = {Alman, Josh and Chattopadhyay, Arkadev and Williams, Ryan}, title = {{Sparsity Lower Bounds for Probabilistic Polynomials}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {3:1--3:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.3}, URN = {urn:nbn:de:0030-drops-226316}, doi = {10.4230/LIPIcs.ITCS.2025.3}, annote = {Keywords: Probabilistic Polynomials, Sparsity, Orthogonal Vectors, Probabilistic Rank} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, and Qianfan Zhang. A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{alon_et_al:LIPIcs.ITCS.2025.4, author = {Alon, Noga and Gravin, Nick and Pollner, Tristan and Rubinstein, Aviad and Wang, Hongao and Weinberg, S. Matthew and Zhang, Qianfan}, title = {{A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {4:1--4:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.4}, URN = {urn:nbn:de:0030-drops-226329}, doi = {10.4230/LIPIcs.ITCS.2025.4}, annote = {Keywords: Prophet Inequalities, Online Contention Resolution Schemes, Concentration Inequalities} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Antoine Amarilli, Benoît Groz, and Nicole Wein. Edge-Minimum Walk of Modular Length in Polynomial Time. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{amarilli_et_al:LIPIcs.ITCS.2025.5, author = {Amarilli, Antoine and Groz, Beno\^{i}t and Wein, Nicole}, title = {{Edge-Minimum Walk of Modular Length in Polynomial Time}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {5:1--5:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.5}, URN = {urn:nbn:de:0030-drops-226330}, doi = {10.4230/LIPIcs.ITCS.2025.5}, annote = {Keywords: Directed Steiner Network, Modularity} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Noga Amir, Oded Goldreich, and Guy N. Rothblum. Doubly Sub-Linear Interactive Proofs of Proximity. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{amir_et_al:LIPIcs.ITCS.2025.6, author = {Amir, Noga and Goldreich, Oded and Rothblum, Guy N.}, title = {{Doubly Sub-Linear Interactive Proofs of Proximity}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {6:1--6:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.6}, URN = {urn:nbn:de:0030-drops-226345}, doi = {10.4230/LIPIcs.ITCS.2025.6}, annote = {Keywords: Interactive Proof Systems, Interactive Proofs of Proximity, Query Complexity, Read Once Branching Programs, Sub-linear} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{ananth_et_al:LIPIcs.ITCS.2025.7, author = {Ananth, Prabhanjan and Kaleoglu, Fatih and Yuen, Henry}, title = {{Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {7:1--7:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.7}, URN = {urn:nbn:de:0030-drops-226352}, doi = {10.4230/LIPIcs.ITCS.2025.7}, annote = {Keywords: Quantum, Haar, unclonable encryption} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger. Single-Round Proofs of Quantumness from Knowledge Assumptions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{arabadjieva_et_al:LIPIcs.ITCS.2025.8, author = {Arabadjieva, Petia and Gheorghiu, Alexandru and Gitton, Victor and Metger, Tony}, title = {{Single-Round Proofs of Quantumness from Knowledge Assumptions}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.8}, URN = {urn:nbn:de:0030-drops-226364}, doi = {10.4230/LIPIcs.ITCS.2025.8}, annote = {Keywords: Proofs of quantumness, Knowledge assumptions, Learning with errors, Decisional Diffie-Hellman} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Itai Arad and Miklos Santha. The Local Hamiltonian Problem for Quasi-Quantum States: A Toy Model for the Quantum PCP Conjecture (Extended Abstract). In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, p. 9:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{arad_et_al:LIPIcs.ITCS.2025.9, author = {Arad, Itai and Santha, Miklos}, title = {{The Local Hamiltonian Problem for Quasi-Quantum States: A Toy Model for the Quantum PCP Conjecture}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {9:1--9:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.9}, URN = {urn:nbn:de:0030-drops-226377}, doi = {10.4230/LIPIcs.ITCS.2025.9}, annote = {Keywords: Quantum Complexity, Probability Checkable Proofs, Local Hamiltonians} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, and Juba Ziani. Algorithmic Collusion Without Threats. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{arunachaleswaran_et_al:LIPIcs.ITCS.2025.10, author = {Arunachaleswaran, Eshwar Ram and Collina, Natalie and Kannan, Sampath and Roth, Aaron and Ziani, Juba}, title = {{Algorithmic Collusion Without Threats}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {10:1--10:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.10}, URN = {urn:nbn:de:0030-drops-226386}, doi = {10.4230/LIPIcs.ITCS.2025.10}, annote = {Keywords: Algorithmic Game Theory, Algorithmic Collusion, No-Regret Dynamics} }
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Vahid R. Asadi, Eric Culf, and Alex May. Rank Lower Bounds on Non-Local Quantum Computation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{asadi_et_al:LIPIcs.ITCS.2025.11, author = {Asadi, Vahid R. and Culf, Eric and May, Alex}, title = {{Rank Lower Bounds on Non-Local Quantum Computation}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {11:1--11:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.11}, URN = {urn:nbn:de:0030-drops-226399}, doi = {10.4230/LIPIcs.ITCS.2025.11}, annote = {Keywords: Non-local quantum computation, quantum position-verification, conditional disclosure of secrets} }
Feedback for Dagstuhl Publishing