LIPIcs, Volume 251
ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA
Editors: Yael Tauman Kalai
LIPIcs, Volume 163
ITC 2020, June 17-19, 2020, Boston, MA, USA
Editors: Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 1-2102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Proceedings{taumankalai:LIPIcs.ITCS.2023, title = {{LIPIcs, Volume 251, ITCS 2023, Complete Volume}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {1--2102}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023}, URN = {urn:nbn:de:0030-drops-175027}, doi = {10.4230/LIPIcs.ITCS.2023}, annote = {Keywords: LIPIcs, Volume 251, ITCS 2023, Complete Volume} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{taumankalai:LIPIcs.ITCS.2023.0, author = {Tauman Kalai, Yael}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {0:i--0:xxii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.0}, URN = {urn:nbn:de:0030-drops-175039}, doi = {10.4230/LIPIcs.ITCS.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Amir Abboud and Nathan Wallheimer. Worst-Case to Expander-Case Reductions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abboud_et_al:LIPIcs.ITCS.2023.1, author = {Abboud, Amir and Wallheimer, Nathan}, title = {{Worst-Case to Expander-Case Reductions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {1:1--1:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.1}, URN = {urn:nbn:de:0030-drops-175044}, doi = {10.4230/LIPIcs.ITCS.2023.1}, annote = {Keywords: Fine-Grained Complexity, Expander Decomposition, Reductions, Exact and Parameterized Complexity, Expander Graphs, Triangle, Maximum Matching, Clique, 4-Cycle, Vertex Cover, Dominating Set} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2, author = {Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan}, title = {{Matroid Partition Property and the Secretary Problem}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2}, URN = {urn:nbn:de:0030-drops-175051}, doi = {10.4230/LIPIcs.ITCS.2023.2}, annote = {Keywords: Online algorithms, Matroids, Matroid secretary problem} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov Complexity Characterizes Statistical Zero Knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{allender_et_al:LIPIcs.ITCS.2023.3, author = {Allender, Eric and Hirahara, Shuichi and Tirumala, Harsha}, title = {{Kolmogorov Complexity Characterizes Statistical Zero Knowledge}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.3}, URN = {urn:nbn:de:0030-drops-175063}, doi = {10.4230/LIPIcs.ITCS.2023.3}, annote = {Keywords: Kolmogorov Complexity, Interactive Proofs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Alexandr Andoni, Jarosław Błasiok, and Arnold Filtser. Communication Complexity of Inner Product in Symmetric Normed Spaces. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{andoni_et_al:LIPIcs.ITCS.2023.4, author = {Andoni, Alexandr and B{\l}asiok, Jaros{\l}aw and Filtser, Arnold}, title = {{Communication Complexity of Inner Product in Symmetric Normed Spaces}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {4:1--4:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.4}, URN = {urn:nbn:de:0030-drops-175077}, doi = {10.4230/LIPIcs.ITCS.2023.4}, annote = {Keywords: communication complexity, symmetric norms} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Anurag Anshu and Tony Metger. Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 5:1-5:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{anshu_et_al:LIPIcs.ITCS.2023.5, author = {Anshu, Anurag and Metger, Tony}, title = {{Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {5:1--5:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.5}, URN = {urn:nbn:de:0030-drops-175085}, doi = {10.4230/LIPIcs.ITCS.2023.5}, annote = {Keywords: quantum computing, polynomial approximation, quantum optimization algorithm, QAOA, overlap gap property} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arvind_et_al:LIPIcs.ITCS.2023.6, author = {Arvind, V. and Chatterjee, Abhranil and Ghosal, Utsab and Mukhopadhyay, Partha and Ramya, C.}, title = {{On Identity Testing and Noncommutative Rank Computation over the Free Skew Field}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {6:1--6:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.6}, URN = {urn:nbn:de:0030-drops-175093}, doi = {10.4230/LIPIcs.ITCS.2023.6}, annote = {Keywords: Algebraic Complexity, Identity Testing, Non-commutative rank} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sepehr Assadi, Aaron Bernstein, and Zachary Langley. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2023.7, author = {Assadi, Sepehr and Bernstein, Aaron and Langley, Zachary}, title = {{All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {7:1--7:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.7}, URN = {urn:nbn:de:0030-drops-175106}, doi = {10.4230/LIPIcs.ITCS.2023.7}, annote = {Keywords: Load Balancing, Semi-Streaming Algorithms, Semi-Matching} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{attias_et_al:LIPIcs.ITCS.2023.8, author = {Attias, Idan and Cohen, Edith and Shechner, Moshe and Stemmer, Uri}, title = {{A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {8:1--8:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.8}, URN = {urn:nbn:de:0030-drops-175115}, doi = {10.4230/LIPIcs.ITCS.2023.8}, annote = {Keywords: Streaming, adversarial robustness, differential privacy} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Moshe Babaioff, Nicole Immorlica, Yingkai Li, and Brendan Lucier. Making Auctions Robust to Aftermarkets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{babaioff_et_al:LIPIcs.ITCS.2023.9, author = {Babaioff, Moshe and Immorlica, Nicole and Li, Yingkai and Lucier, Brendan}, title = {{Making Auctions Robust to Aftermarkets}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {9:1--9:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.9}, URN = {urn:nbn:de:0030-drops-175122}, doi = {10.4230/LIPIcs.ITCS.2023.9}, annote = {Keywords: carbon markets, aftermarkets, price of anarchy, multi-unit auctions, posted prices} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, and Krzysztof Pietrzak. Efficiently Testable Circuits. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{baig_et_al:LIPIcs.ITCS.2023.10, author = {Baig, Mirza Ahad and Chakraborty, Suvradip and Dziembowski, Stefan and Ga{\l}\k{a}zka, Ma{\l}gorzata and Lizurej, Tomasz and Pietrzak, Krzysztof}, title = {{Efficiently Testable Circuits}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {10:1--10:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.10}, URN = {urn:nbn:de:0030-drops-175130}, doi = {10.4230/LIPIcs.ITCS.2023.10}, annote = {Keywords: circuit compilers, circuit integrity, circuit testing} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof Scheduling with Predictions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{balkanski_et_al:LIPIcs.ITCS.2023.11, author = {Balkanski, Eric and Gkatzelis, Vasilis and Tan, Xizhi}, title = {{Strategyproof Scheduling with Predictions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {11:1--11:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.11}, URN = {urn:nbn:de:0030-drops-175143}, doi = {10.4230/LIPIcs.ITCS.2023.11}, annote = {Keywords: Mechanism Design with Predictions, Strategyproof Scheduling} }
Feedback for Dagstuhl Publishing