Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny. Certificate Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.32, author = {Chakraborty, Sourav and G\'{a}l, Anna and Laplante, Sophie and Mittal, Rajat and Sunny, Anupa}, title = {{Certificate Games}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {32:1--32: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.32}, URN = {urn:nbn:de:0030-drops-175353}, doi = {10.4230/LIPIcs.ITCS.2023.32}, annote = {Keywords: block sensitivity, boolean function complexity, certificate complexity, query complexity, sensitivity, zero-communication two-player games} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Sander Gribling and Harold Nieuwboer. Improved Quantum Lower and Upper Bounds for Matrix Scaling. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gribling_et_al:LIPIcs.STACS.2022.35, author = {Gribling, Sander and Nieuwboer, Harold}, title = {{Improved Quantum Lower and Upper Bounds for Matrix Scaling}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {35:1--35:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.35}, URN = {urn:nbn:de:0030-drops-158458}, doi = {10.4230/LIPIcs.STACS.2022.35}, annote = {Keywords: Matrix scaling, quantum algorithms, lower bounds} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Nathan Lindzey and Ansis Rosmanis. A Tight Lower Bound For Non-Coherent Index Erasure. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 59:1-59:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lindzey_et_al:LIPIcs.ITCS.2020.59, author = {Lindzey, Nathan and Rosmanis, Ansis}, title = {{A Tight Lower Bound For Non-Coherent Index Erasure}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {59:1--59:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.59}, URN = {urn:nbn:de:0030-drops-117446}, doi = {10.4230/LIPIcs.ITCS.2020.59}, annote = {Keywords: General Adversary Method, Quantum Query Complexity, Association Schemes, Krein Parameters, Representation Theory} }
Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno. Robust Bell Inequalities from Communication Complexity. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{laplante_et_al:LIPIcs.TQC.2016.5, author = {Laplante, Sophie and Lauri\`{e}re, Mathieu and Nolin, Alexandre and Roland, J\'{e}r\'{e}mie and Senno, Gabriel}, title = {{Robust Bell Inequalities from Communication Complexity}}, booktitle = {11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)}, pages = {5:1--5:24}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.5}, URN = {urn:nbn:de:0030-drops-66867}, doi = {10.4230/LIPIcs.TQC.2016.5}, annote = {Keywords: Communication complexity, Bell inequalities, nonlocality, detector efficiency} }
Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Mathieu Brandeho and Jérémie Roland. A Universal Adiabatic Quantum Query Algorithm. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 163-179, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{brandeho_et_al:LIPIcs.TQC.2015.163, author = {Brandeho, Mathieu and Roland, J\'{e}r\'{e}mie}, title = {{A Universal Adiabatic Quantum Query Algorithm}}, booktitle = {10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)}, pages = {163--179}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-96-5}, ISSN = {1868-8969}, year = {2015}, volume = {44}, editor = {Beigi, Salman and K\"{o}nig, Robert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.163}, URN = {urn:nbn:de:0030-drops-55556}, doi = {10.4230/LIPIcs.TQC.2015.163}, annote = {Keywords: Quantum Algorithms, Query Complexity, Adiabatic Quantum Computation, Adversary Method} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Loïck Magnin and Jérémie Roland. Explicit relation between all lower bound techniques for quantum query complexity. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 434-445, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{magnin_et_al:LIPIcs.STACS.2013.434, author = {Magnin, Lo\"{i}ck and Roland, J\'{e}r\'{e}mie}, title = {{Explicit relation between all lower bound techniques for quantum query complexity}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {434--445}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.434}, URN = {urn:nbn:de:0030-drops-39548}, doi = {10.4230/LIPIcs.STACS.2013.434}, annote = {Keywords: Quantum computation, lower bound, adversary method, polynomial method} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Marc Kaplan, Iordanis Kerenidis, Sophie Laplante, and Jérémie Roland. Non-Local Box Complexity and Secure Function Evaluation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 239-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{kaplan_et_al:LIPIcs.FSTTCS.2009.2322, author = {Kaplan, Marc and Kerenidis, Iordanis and Laplante, Sophie and Roland, J\'{e}r\'{e}mie}, title = {{Non-Local Box Complexity and Secure Function Evaluation}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {239--250}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2322}, URN = {urn:nbn:de:0030-drops-23226}, doi = {10.4230/LIPIcs.FSTTCS.2009.2322}, annote = {Keywords: Communication complexity, non-locality, non-local boxes, secure function evaluation} }
Feedback for Dagstuhl Publishing