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 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Yassine Hamoudi and Frédéric Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 1:1-1:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hamoudi_et_al:LIPIcs.TQC.2021.1, author = {Hamoudi, Yassine and Magniez, Fr\'{e}d\'{e}ric}, title = {{Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs}}, booktitle = {16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)}, pages = {1:1--1:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-198-6}, ISSN = {1868-8969}, year = {2021}, volume = {197}, editor = {Hsieh, Min-Hsiu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.1}, URN = {urn:nbn:de:0030-drops-139961}, doi = {10.4230/LIPIcs.TQC.2021.1}, annote = {Keywords: Quantum computing, query complexity, lower bound, time-space tradeoff} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{buhrman_et_al:LIPIcs.STACS.2021.19, author = {Buhrman, Harry and Patro, Subhasree and Speelman, Florian}, title = {{A Framework of Quantum Strong Exponential-Time Hypotheses}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {19:1--19:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.19}, URN = {urn:nbn:de:0030-drops-136642}, doi = {10.4230/LIPIcs.STACS.2021.19}, annote = {Keywords: complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Frédéric Magniez and Ashwin Nayak. Quantum Distributed Complexity of Set Disjointness on a Line. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 82:1-82:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{magniez_et_al:LIPIcs.ICALP.2020.82, author = {Magniez, Fr\'{e}d\'{e}ric and Nayak, Ashwin}, title = {{Quantum Distributed Complexity of Set Disjointness on a Line}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {82:1--82:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.82}, URN = {urn:nbn:de:0030-drops-124892}, doi = {10.4230/LIPIcs.ICALP.2020.82}, annote = {Keywords: Quantum distributed computing, Set Disjointness, communication complexity, query complexity} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 23:1-23:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{izumi_et_al:LIPIcs.STACS.2020.23, author = {Izumi, Taisuke and Le Gall, Fran\c{c}ois and Magniez, Fr\'{e}d\'{e}ric}, title = {{Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {23:1--23:13}, 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.23}, URN = {urn:nbn:de:0030-drops-118840}, doi = {10.4230/LIPIcs.STACS.2020.23}, annote = {Keywords: Quantum computing, distributed computing, CONGEST model} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Simon Apers. Quantum Walk Sampling by Growing Seed Sets. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 9:1-9:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{apers:LIPIcs.ESA.2019.9, author = {Apers, Simon}, title = {{Quantum Walk Sampling by Growing Seed Sets}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {9:1--9:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.9}, URN = {urn:nbn:de:0030-drops-111300}, doi = {10.4230/LIPIcs.ESA.2019.9}, annote = {Keywords: Quantum algorithms, Quantum walks, Connectivity, Graph theory} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Aleksandrs Belovs. Quantum Algorithms for Classical Probability Distributions. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 16:1-16:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{belovs:LIPIcs.ESA.2019.16, author = {Belovs, Aleksandrs}, title = {{Quantum Algorithms for Classical Probability Distributions}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {16:1--16:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.16}, URN = {urn:nbn:de:0030-drops-111370}, doi = {10.4230/LIPIcs.ESA.2019.16}, annote = {Keywords: quantum query complexity, quantum adversary method, distinguishing probability distributions, Hellinger distance} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev’s Inequality and Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 69:1-69:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{hamoudi_et_al:LIPIcs.ICALP.2019.69, author = {Hamoudi, Yassine and Magniez, Fr\'{e}d\'{e}ric}, title = {{Quantum Chebyshev’s Inequality and Applications}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {69:1--69:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.69}, URN = {urn:nbn:de:0030-drops-106458}, doi = {10.4230/LIPIcs.ICALP.2019.69}, annote = {Keywords: Quantum algorithms, approximation algorithms, sublinear-time algorithms, Monte Carlo method, streaming algorithms, subgraph counting} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Shalev Ben-David and Robin Kothari. Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bendavid_et_al:LIPIcs.TQC.2019.2, author = {Ben-David, Shalev and Kothari, Robin}, title = {{Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {2:1--2:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.2}, URN = {urn:nbn:de:0030-drops-103944}, doi = {10.4230/LIPIcs.TQC.2019.2}, annote = {Keywords: Quantum query complexity, quantum algorithms} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Lucas Boczkowski, Iordanis Kerenidis, and Frédéric Magniez. Streaming Communication Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 130:1-130:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{boczkowski_et_al:LIPIcs.ICALP.2017.130, author = {Boczkowski, Lucas and Kerenidis, Iordanis and Magniez, Fr\'{e}d\'{e}ric}, title = {{Streaming Communication Protocols}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {130:1--130:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.130}, URN = {urn:nbn:de:0030-drops-74404}, doi = {10.4230/LIPIcs.ICALP.2017.130}, annote = {Keywords: Networks, Communication Complexity, Streaming Algorithms} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended Learning Graphs for Triangle Finding. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 20:1-20:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{carette_et_al:LIPIcs.STACS.2017.20, author = {Carette, Titouan and Lauri\`{e}re, Mathieu and Magniez, Fr\'{e}d\'{e}ric}, title = {{Extended Learning Graphs for Triangle Finding}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.20}, URN = {urn:nbn:de:0030-drops-70132}, doi = {10.4230/LIPIcs.STACS.2017.20}, annote = {Keywords: Quantum query complexity, learning graphs, triangle finding} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Varun Kanade, Nikos Leonardos, and Frédéric Magniez. Stable Matching with Evolving Preferences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 36:1-36:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{kanade_et_al:LIPIcs.APPROX-RANDOM.2016.36, author = {Kanade, Varun and Leonardos, Nikos and Magniez, Fr\'{e}d\'{e}ric}, title = {{Stable Matching with Evolving Preferences}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {36:1--36:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.36}, URN = {urn:nbn:de:0030-drops-66597}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.36}, annote = {Keywords: Stable Matching, Dynamic Data} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming Property Testing of Visibly Pushdown Languages. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 43:1-43:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{francois_et_al:LIPIcs.ESA.2016.43, author = {Fran\c{c}ois, Nathana\"{e}l and Magniez, Fr\'{e}d\'{e}ric and de Rougemont, Michel and Serre, Olivier}, title = {{Streaming Property Testing of Visibly Pushdown Languages}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {43:1--43:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.43}, URN = {urn:nbn:de:0030-drops-63559}, doi = {10.4230/LIPIcs.ESA.2016.43}, annote = {Keywords: Streaming Algorithm, Property Testing, Visibly Pushdown Languages} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Cedric Yen-Yu Lin and Han-Hsuan Lin. Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 537-566, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{lin_et_al:LIPIcs.CCC.2015.537, author = {Lin, Cedric Yen-Yu and Lin, Han-Hsuan}, title = {{Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {537--566}, 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.537}, URN = {urn:nbn:de:0030-drops-50635}, doi = {10.4230/LIPIcs.CCC.2015.537}, annote = {Keywords: Quantum Algorithms, Query Complexity, Elitzur-Vaidman Bomb Tester, Adversary Method, Maximum Bipartite Matching} }
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