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 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 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Nathanaël François, Rahul Jain, and Frédéric Magniez. Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 654-668, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{francois_et_al:LIPIcs.APPROX-RANDOM.2014.654, author = {Fran\c{c}ois, Nathana\"{e}l and Jain, Rahul and Magniez, Fr\'{e}d\'{e}ric}, title = {{Unidirectional Input/Output Streaming Complexity of Reversal and Sorting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {654--668}, 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.654}, URN = {urn:nbn:de:0030-drops-47298}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.654}, annote = {Keywords: Streaming Algorithms, Multiple Streams, Reversal, Sorting} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Nathanael Francois and Frédéric Magniez. Streaming Complexity of Checking Priority Queues. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 454-465, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{francois_et_al:LIPIcs.STACS.2013.454, author = {Francois, Nathanael and Magniez, Fr\'{e}d\'{e}ric}, title = {{Streaming Complexity of Checking Priority Queues}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {454--465}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.454}, URN = {urn:nbn:de:0030-drops-39561}, doi = {10.4230/LIPIcs.STACS.2013.454}, annote = {Keywords: Streaming Algorithms, Communication Complexity, Priority Queue} }
Feedback for Dagstuhl Publishing