Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Xin Li and Yan Zhong. Two-Source and Affine Non-Malleable Extractors for Small Entropy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 108:1-108:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.108, author = {Li, Xin and Zhong, Yan}, title = {{Two-Source and Affine Non-Malleable Extractors for Small Entropy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {108:1--108:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.108}, URN = {urn:nbn:de:0030-drops-202512}, doi = {10.4230/LIPIcs.ICALP.2024.108}, annote = {Keywords: Randomness Extractors, Non-malleable, Two-source, Affine} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Vladimir V. Podolskii and Dmitrii Sluch. One-Way Communication Complexity of Partial XOR Functions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 116:1-116:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{podolskii_et_al:LIPIcs.ICALP.2024.116, author = {Podolskii, Vladimir V. and Sluch, Dmitrii}, title = {{One-Way Communication Complexity of Partial XOR Functions}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {116:1--116:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.116}, URN = {urn:nbn:de:0030-drops-202591}, doi = {10.4230/LIPIcs.ICALP.2024.116}, annote = {Keywords: Partial functions, XOR functions, communication complexity, decision trees, covering codes} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, and Kamesh Munagala. Online Learning and Bandits with Queried Hints. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bhaskara_et_al:LIPIcs.ITCS.2023.16, author = {Bhaskara, Aditya and Gollapudi, Sreenivas and Im, Sungjin and Kollias, Kostas and Munagala, Kamesh}, title = {{Online Learning and Bandits with Queried Hints}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {16:1--16: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.16}, URN = {urn:nbn:de:0030-drops-175197}, doi = {10.4230/LIPIcs.ITCS.2023.16}, annote = {Keywords: Online learning, multi-armed bandits, regret} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bodwin_et_al:LIPIcs.ITCS.2023.20, author = {Bodwin, Greg and Dinitz, Michael and Nazari, Yasamin}, title = {{Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {20:1--20: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.20}, URN = {urn:nbn:de:0030-drops-175231}, doi = {10.4230/LIPIcs.ITCS.2023.20}, annote = {Keywords: Emulators, Fault Tolerance, Girth Conjecture} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer. Improved Monotonicity Testers via Hypercube Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.25, author = {Braverman, Mark and Khot, Subhash and Kindler, Guy and Minzer, Dor}, title = {{Improved Monotonicity Testers via Hypercube Embeddings}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {25:1--25: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.25}, URN = {urn:nbn:de:0030-drops-175285}, doi = {10.4230/LIPIcs.ITCS.2023.25}, annote = {Keywords: Property Testing, Monotonicity Testing, Isoperimetric Inequalities} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Mark Braverman and Dor Minzer. Rounding via Low Dimensional Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 26:1-26:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.26, author = {Braverman, Mark and Minzer, Dor}, title = {{Rounding via Low Dimensional Embeddings}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {26:1--26:30}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.26}, URN = {urn:nbn:de:0030-drops-175291}, doi = {10.4230/LIPIcs.ITCS.2023.26}, annote = {Keywords: Parallel Repetition, Small Set Expanders, Semi-Definite Programs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estimations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 48:1-48:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{epasto_et_al:LIPIcs.ITCS.2023.48, author = {Epasto, Alessandro and Mao, Jieming and Medina, Andres Munoz and Mirrokni, Vahab and Vassilvitskii, Sergei and Zhong, Peilin}, title = {{Differentially Private Continual Releases of Streaming Frequency Moment Estimations}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {48:1--48: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.48}, URN = {urn:nbn:de:0030-drops-175513}, doi = {10.4230/LIPIcs.ITCS.2023.48}, annote = {Keywords: Differential Privacy, Continual Release, Sliding Window, Streaming Algorithms, Distinct Elements, Frequency Moment Estimation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Hamza Fawzi, Omar Fawzi, and Samuel O. Scalet. A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 49:1-49:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fawzi_et_al:LIPIcs.ITCS.2023.49, author = {Fawzi, Hamza and Fawzi, Omar and Scalet, Samuel O.}, title = {{A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {49:1--49:6}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.49}, URN = {urn:nbn:de:0030-drops-175520}, doi = {10.4230/LIPIcs.ITCS.2023.49}, annote = {Keywords: One-dimensional quantum systems, Free energy} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 52:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gaitonde_et_al:LIPIcs.ITCS.2023.52, author = {Gaitonde, Jason and Li, Yingkai and Light, Bar and Lucier, Brendan and Slivkins, Aleksandrs}, title = {{Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {52:1--52:1}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.52}, URN = {urn:nbn:de:0030-drops-175557}, doi = {10.4230/LIPIcs.ITCS.2023.52}, annote = {Keywords: repeated auctions with budgets, pacing, learning in auctions} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi. Private Counting of Distinct and k-Occurring Items in Time Windows. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 55:1-55:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ITCS.2023.55, author = {Ghazi, Badih and Kumar, Ravi and Nelson, Jelani and Manurangsi, Pasin}, title = {{Private Counting of Distinct and k-Occurring Items in Time Windows}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {55:1--55: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.55}, URN = {urn:nbn:de:0030-drops-175580}, doi = {10.4230/LIPIcs.ITCS.2023.55}, annote = {Keywords: Differential Privacy, Algorithms, Distinct Elements, Time Windows} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, and João Ribeiro. Asynchronous Multi-Party Quantum Computation. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 62:1-62:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{goyal_et_al:LIPIcs.ITCS.2023.62, author = {Goyal, Vipul and Liu-Zhang, Chen-Da and Raizes, Justin and Ribeiro, Jo\~{a}o}, title = {{Asynchronous Multi-Party Quantum Computation}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {62:1--62: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62}, URN = {urn:nbn:de:0030-drops-175655}, doi = {10.4230/LIPIcs.ITCS.2023.62}, annote = {Keywords: Quantum Cryptography, Multiparty Computation, Asynchronous} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{grewal_et_al:LIPIcs.ITCS.2023.64, author = {Grewal, Sabee and Iyer, Vishnu and Kretschmer, William and Liang, Daniel}, title = {{Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {64:1--64:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.64}, URN = {urn:nbn:de:0030-drops-175670}, doi = {10.4230/LIPIcs.ITCS.2023.64}, annote = {Keywords: Pseudorandom quantum states, Clifford + T, Haar random, Bell sampling, stabilizer formalism, stabilizer extent, stabilizer fidelity, learning theory, complexity theory} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Martin Hirt and Marta Mularczyk. Efficient MPC with a Mixed Adversary. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hirt_et_al:LIPIcs.ITC.2020.3, author = {Hirt, Martin and Mularczyk, Marta}, title = {{Efficient MPC with a Mixed Adversary}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {3:1--3:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.3}, URN = {urn:nbn:de:0030-drops-121083}, doi = {10.4230/LIPIcs.ITC.2020.3}, annote = {Keywords: Multi-party Computation, Communication Cost} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang. Practical Relativistic Zero-Knowledge for NP. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{crepeau_et_al:LIPIcs.ITC.2020.4, author = {Cr\'{e}peau, Claude and Massenet, Arnaud Y. and Salvail, Louis and Stinchcombe, Lucas Shigeru and Yang, Nan}, title = {{Practical Relativistic Zero-Knowledge for NP}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.4}, URN = {urn:nbn:de:0030-drops-121091}, doi = {10.4230/LIPIcs.ITC.2020.4}, annote = {Keywords: Multi-Prover Interactive Proofs, Relativistic Commitments, 3-COLorability, Quantum Entanglement, Non-Locality} }
Feedback for Dagstuhl Publishing