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 200, 36th Computational Complexity Conference (CCC 2021)
Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 30:1-30:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{anshu_et_al:LIPIcs.CCC.2021.30, author = {Anshu, Anurag and Ben-David, Shalev and Kundu, Srijita}, title = {{On Query-To-Communication Lifting for Adversary Bounds}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {30:1--30:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30}, URN = {urn:nbn:de:0030-drops-143042}, doi = {10.4230/LIPIcs.CCC.2021.30}, annote = {Keywords: Quantum computing, query complexity, communication complexity, lifting theorems, adversary method} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Srinivasan Arunachalam and Supartha Podder. Communication Memento: Memoryless Communication Complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2021.61, author = {Arunachalam, Srinivasan and Podder, Supartha}, title = {{Communication Memento: Memoryless Communication Complexity}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {61:1--61:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.61}, URN = {urn:nbn:de:0030-drops-136007}, doi = {10.4230/LIPIcs.ITCS.2021.61}, annote = {Keywords: Communication complexity, space complexity, branching programs, garden-hose model, quantum computing} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Mathieu Laurière and Dave Touchette. The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, p. 47:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{lauriere_et_al:LIPIcs.ITCS.2017.47, author = {Lauri\`{e}re, Mathieu and Touchette, Dave}, title = {{The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {47:1--47:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.47}, URN = {urn:nbn:de:0030-drops-81898}, doi = {10.4230/LIPIcs.ITCS.2017.47}, annote = {Keywords: Communication Complexity, Information Complexity, Quantum Computation and Information} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Ashwin Nayak and Dave Touchette. Augmented Index and Quantum Streaming Algorithms for DYCK(2). In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{nayak_et_al:LIPIcs.CCC.2017.23, author = {Nayak, Ashwin and Touchette, Dave}, title = {{Augmented Index and Quantum Streaming Algorithms for DYCK(2)}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {23:1--23:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.23}, URN = {urn:nbn:de:0030-drops-75437}, doi = {10.4230/LIPIcs.CCC.2017.23}, annote = {Keywords: Quantum streaming algorithms, Space complexity, Quantum communication complexity, Quantum information cost, DYCK(2), Augmented Index} }