Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Jop Briët and Francisco Escudero Gutiérrez. On Converses to the Polynomial Method. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{briet_et_al:LIPIcs.TQC.2022.6, author = {Bri\"{e}t, Jop and Escudero Guti\'{e}rrez, Francisco}, title = {{On Converses to the Polynomial Method}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {6:1--6:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-237-2}, ISSN = {1868-8969}, year = {2022}, volume = {232}, editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.6}, URN = {urn:nbn:de:0030-drops-165139}, doi = {10.4230/LIPIcs.TQC.2022.6}, annote = {Keywords: Quantum query complexity, polynomial method, completely bounded polynomials} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ambainis_et_al:LIPIcs.MFCS.2020.8, author = {Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis and Khadiev, Kamil and K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Shen, Yixin and Smotrovs, Juris and Vihrovs, Jevg\={e}nijs}, title = {{Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.8}, URN = {urn:nbn:de:0030-drops-126774}, doi = {10.4230/LIPIcs.MFCS.2020.8}, annote = {Keywords: Quantum query complexity, Quantum algorithms, Dyck language, Grid path} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Eric Blais and Joshua Brody. Optimal Separation and Strong Direct Sum for Randomized Query Complexity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blais_et_al:LIPIcs.CCC.2019.29, author = {Blais, Eric and Brody, Joshua}, title = {{Optimal Separation and Strong Direct Sum for Randomized Query Complexity}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {29:1--29: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.29}, URN = {urn:nbn:de:0030-drops-108511}, doi = {10.4230/LIPIcs.CCC.2019.29}, annote = {Keywords: Decision trees, query complexity, communication complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality Alone Does not Simulate Randomness. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.14, author = {Chattopadhyay, Arkadev and Lovett, Shachar and Vinyals, Marc}, title = {{Equality Alone Does not Simulate Randomness}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {14:1--14:11}, 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.14}, URN = {urn:nbn:de:0030-drops-108368}, doi = {10.4230/LIPIcs.CCC.2019.14}, annote = {Keywords: Communication lower bound, derandomization} }
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 50, 31st Conference on Computational Complexity (CCC 2016)
Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, and Juris Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 25:1-25:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2016.25, author = {Aaronson, Scott and Ambainis, Andris and Iraids, Janis and Kokainis, Martins and Smotrovs, Juris}, title = {{Polynomials, Quantum Query Complexity, and Grothendieck's Inequality}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {25:1--25:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.25}, URN = {urn:nbn:de:0030-drops-58394}, doi = {10.4230/LIPIcs.CCC.2016.25}, annote = {Keywords: quantum algorithms, Boolean functions, approximation by polynomials, Grothendieck's inequality} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Sagnik Mukhopadhyay and Swagato Sanyal. Towards Better Separation between Deterministic and Randomized Query Complexity. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 206-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{mukhopadhyay_et_al:LIPIcs.FSTTCS.2015.206, author = {Mukhopadhyay, Sagnik and Sanyal, Swagato}, title = {{Towards Better Separation between Deterministic and Randomized Query Complexity}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {206--220}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.206}, URN = {urn:nbn:de:0030-drops-56467}, doi = {10.4230/LIPIcs.FSTTCS.2015.206}, annote = {Keywords: Deterministic Decision Tree, Randomized Decision Tree, Query Complexity, Models of Computation.} }
Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Andris Ambainis, Janis Iraids, and Juris Smotrovs. Exact Quantum Query Complexity of EXACT and THRESHOLD. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 263-269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{ambainis_et_al:LIPIcs.TQC.2013.263, author = {Ambainis, Andris and Iraids, Janis and Smotrovs, Juris}, title = {{Exact Quantum Query Complexity of EXACT and THRESHOLD}}, booktitle = {8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)}, pages = {263--269}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-55-2}, ISSN = {1868-8969}, year = {2013}, volume = {22}, editor = {Severini, Simone and Brandao, Fernando}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.263}, URN = {urn:nbn:de:0030-drops-43261}, doi = {10.4230/LIPIcs.TQC.2013.263}, annote = {Keywords: Quantum query algorithms, Complexity of Boolean functions} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Andris Ambainis, Arturs Backurs, Juris Smotrovs, and Ronald de Wolf. Optimal quantum query bounds for almost all Boolean functions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 446-453, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{ambainis_et_al:LIPIcs.STACS.2013.446, author = {Ambainis, Andris and Backurs, Arturs and Smotrovs, Juris and de Wolf, Ronald}, title = {{Optimal quantum query bounds for almost all Boolean functions}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {446--453}, 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.446}, URN = {urn:nbn:de:0030-drops-39557}, doi = {10.4230/LIPIcs.STACS.2013.446}, annote = {Keywords: Quantum computing, query complexity, lower bounds, polynomial method} }
Feedback for Dagstuhl Publishing