Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs. Improved Algorithm and Lower Bound for Variable Time Quantum Search. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ambainis_et_al:LIPIcs.TQC.2023.7, author = {Ambainis, Andris and Kokainis, Martins and Vihrovs, Jevg\={e}nijs}, title = {{Improved Algorithm and Lower Bound for Variable Time Quantum Search}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-283-9}, ISSN = {1868-8969}, year = {2023}, volume = {266}, editor = {Fawzi, Omar and Walter, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.7}, URN = {urn:nbn:de:0030-drops-183177}, doi = {10.4230/LIPIcs.TQC.2023.7}, annote = {Keywords: quantum search, amplitude amplification} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Adam Glos, Martins Kokainis, Ryuhei Mori, and Jevgēnijs Vihrovs. Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 50:1-50:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{glos_et_al:LIPIcs.MFCS.2021.50, author = {Glos, Adam and Kokainis, Martins and Mori, Ryuhei and Vihrovs, Jevg\={e}nijs}, title = {{Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {50:1--50:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.50}, URN = {urn:nbn:de:0030-drops-144901}, doi = {10.4230/LIPIcs.MFCS.2021.50}, annote = {Keywords: Quantum query complexity, Dynamic programming, Lattice graphs} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{ambainis_et_al:LIPIcs.STACS.2018.8, author = {Ambainis, Andris and Kokainis, Martins and Prusis, Krisjanis and Vihrovs, Jevgenijs}, title = {{All Classical Adversary Methods are Equivalent for Total Functions}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf 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.2018.8}, URN = {urn:nbn:de:0030-drops-84953}, doi = {10.4230/LIPIcs.STACS.2018.8}, annote = {Keywords: Randomized Query Complexity, Lower Bounds, Adversary Bounds, Fractional Block Sensitivity} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Andris Ambainis, Martins Kokainis, and Robin Kothari. Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 4:1-4:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{ambainis_et_al:LIPIcs.CCC.2016.4, author = {Ambainis, Andris and Kokainis, Martins and Kothari, Robin}, title = {{Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {4:1--4:14}, 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.4}, URN = {urn:nbn:de:0030-drops-58471}, doi = {10.4230/LIPIcs.CCC.2016.4}, annote = {Keywords: Query Complexity, Communication Complexity, Subcube Partition Complexity, Partition Bound} }
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} }
Feedback for Dagstuhl Publishing