Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
François Le Gall. Quantum Distributed Computing: Potential and Limitations (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{legall:LIPIcs.OPODIS.2023.2, author = {Le Gall, Fran\c{c}ois}, title = {{Quantum Distributed Computing: Potential and Limitations}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.2}, URN = {urn:nbn:de:0030-drops-194925}, doi = {10.4230/LIPIcs.OPODIS.2023.2}, annote = {Keywords: Quantum computing, distributed algorithms, CONGEST model, LOCAL model} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Supartha Podder, Penghui Yao, and Zekun Ye. On the Fine-Grained Query Complexity of Symmetric Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 55:1-55:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{podder_et_al:LIPIcs.ISAAC.2023.55, author = {Podder, Supartha and Yao, Penghui and Ye, Zekun}, title = {{On the Fine-Grained Query Complexity of Symmetric Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {55:1--55:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.55}, URN = {urn:nbn:de:0030-drops-193570}, doi = {10.4230/LIPIcs.ISAAC.2023.55}, annote = {Keywords: Query complexity, Symmetric functions, Quantum advantages} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Minglong Qin and Penghui Yao. Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 97:1-97:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{qin_et_al:LIPIcs.ICALP.2023.97, author = {Qin, Minglong and Yao, Penghui}, title = {{Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {97:1--97:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.97}, URN = {urn:nbn:de:0030-drops-181499}, doi = {10.4230/LIPIcs.ICALP.2023.97}, annote = {Keywords: Fully quantum nonlocal games, Fourier analysis, Dimension reduction} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Penghui Yao, Yitong Yin, and Xinyuan Zhang. Polynomial-Time Approximation of Zero-Free Partition Functions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 108:1-108:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{yao_et_al:LIPIcs.ICALP.2022.108, author = {Yao, Penghui and Yin, Yitong and Zhang, Xinyuan}, title = {{Polynomial-Time Approximation of Zero-Free Partition Functions}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {108:1--108:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.108}, URN = {urn:nbn:de:0030-drops-164494}, doi = {10.4230/LIPIcs.ICALP.2022.108}, annote = {Keywords: partition function, zero-freeness, local Hamiltonian} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower Bounds for Function Inversion with Quantum Advice. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chung_et_al:LIPIcs.ITC.2020.8, author = {Chung, Kai-Min and Liao, Tai-Ning and Qian, Luowen}, title = {{Lower Bounds for Function Inversion with Quantum Advice}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {8:1--8:15}, 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.8}, URN = {urn:nbn:de:0030-drops-121134}, doi = {10.4230/LIPIcs.ITC.2020.8}, annote = {Keywords: Cryptanalysis, Data Structures, Quantum Query Complexity} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45, author = {Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald}, title = {{Improved Bounds on Fourier Entropy and Min-Entropy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45}, URN = {urn:nbn:de:0030-drops-119062}, doi = {10.4230/LIPIcs.STACS.2020.45}, annote = {Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13, author = {Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory}, title = {{Optimality of Linear Sketching Under Modular Updates}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.13}, URN = {urn:nbn:de:0030-drops-108355}, doi = {10.4230/LIPIcs.CCC.2019.13}, annote = {Keywords: communication complexity, linear sketching, streaming algorithm} }
Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Anurag Anshu, Ankit Garg, Aram W. Harrow, and Penghui Yao. Lower Bound on Expected Communication Cost of Quantum Huffman Coding. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 3:1-3:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{anshu_et_al:LIPIcs.TQC.2016.3, author = {Anshu, Anurag and Garg, Ankit and Harrow, Aram W. and Yao, Penghui}, title = {{Lower Bound on Expected Communication Cost of Quantum Huffman Coding}}, booktitle = {11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)}, pages = {3:1--3:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-019-4}, ISSN = {1868-8969}, year = {2016}, volume = {61}, editor = {Broadbent, Anne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.3}, URN = {urn:nbn:de:0030-drops-66843}, doi = {10.4230/LIPIcs.TQC.2016.3}, annote = {Keywords: Quantum information, quantum communication, expected communica- tion cost, huffman coding} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Kai-Min Chung, Xiaodi Wu, and Henry Yuen. Parallel Repetition for Entangled k-player Games via Fast Quantum Search. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 512-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chung_et_al:LIPIcs.CCC.2015.512, author = {Chung, Kai-Min and Wu, Xiaodi and Yuen, Henry}, title = {{Parallel Repetition for Entangled k-player Games via Fast Quantum Search}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {512--536}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.512}, URN = {urn:nbn:de:0030-drops-50727}, doi = {10.4230/LIPIcs.CCC.2015.512}, annote = {Keywords: Parallel repetition, quantum entanglement, communication complexity} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 545-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{brody_et_al:LIPIcs.APPROX-RANDOM.2014.545, author = {Brody, Joshua and Chakrabarti, Amit and Kondapally, Ranganath and Woodruff, David P. and Yaroslavtsev, Grigory}, title = {{Certifying Equality With Limited Interaction}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {545--581}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.545}, URN = {urn:nbn:de:0030-drops-47229}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.545}, annote = {Keywords: equality, communication complexity, information complexity} }
Feedback for Dagstuhl Publishing