Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Supartha Podder, Penghui Yao, and Zekun Ye. On the Fine-Grained Query Complexity of Symmetric Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 55:1-55:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{podder_et_al:LIPIcs.ISAAC.2023.55, author = {Podder, Supartha and Yao, Penghui and Ye, Zekun}, title = {{On the Fine-Grained Query Complexity of Symmetric Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {55:1--55:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.55}, URN = {urn:nbn:de:0030-drops-193570}, doi = {10.4230/LIPIcs.ISAAC.2023.55}, annote = {Keywords: Query complexity, Symmetric functions, Quantum advantages} }
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 264, 38th Computational Complexity Conference (CCC 2023)
Andris Ambainis and Aleksandrs Belovs. An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 24:1-24:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ambainis_et_al:LIPIcs.CCC.2023.24, author = {Ambainis, Andris and Belovs, Aleksandrs}, title = {{An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {24:1--24:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.24}, URN = {urn:nbn:de:0030-drops-182943}, doi = {10.4230/LIPIcs.CCC.2023.24}, annote = {Keywords: Polynomials, Quantum Adversary Bound, Separations in Query Complexity} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Uma Girish, Ran Raz, and Wei Zhan. Lower Bounds for XOR of Forrelations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 52:1-52:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.52, author = {Girish, Uma and Raz, Ran and Zhan, Wei}, title = {{Lower Bounds for XOR of Forrelations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {52:1--52:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.52}, URN = {urn:nbn:de:0030-drops-147453}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.52}, annote = {Keywords: Forrelation, Quasipolynomial, Separation, Quantum versus Classical, Xor} }
Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Andris Ambainis, Kaspars Balodis, and Jānis Iraids. A Note About Claw Function with a Small Range. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 6:1-6:5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ambainis_et_al:LIPIcs.TQC.2021.6, author = {Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis}, title = {{A Note About Claw Function with a Small Range}}, booktitle = {16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)}, pages = {6:1--6:5}, 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.6}, URN = {urn:nbn:de:0030-drops-140013}, doi = {10.4230/LIPIcs.TQC.2021.6}, annote = {Keywords: collision, claw, quantum query complexity} }
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 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 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Andris Ambainis and Nikita Larka. Quantum Algorithms for Computational Geometry Problems. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 9:1-9:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ambainis_et_al:LIPIcs.TQC.2020.9, author = {Ambainis, Andris and Larka, Nikita}, title = {{Quantum Algorithms for Computational Geometry Problems}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {9:1--9:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.9}, URN = {urn:nbn:de:0030-drops-120687}, doi = {10.4230/LIPIcs.TQC.2020.9}, annote = {Keywords: Quantum algorithms, quantum search, computational geometry, 3Sum problem, amplitude amplification} }
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} }
Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Andris Ambainis and Janis Iraids. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 146-156, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{ambainis_et_al:LIPIcs.TQC.2013.146, author = {Ambainis, Andris and Iraids, Janis}, title = {{Provable Advantage for Quantum Strategies in Random Symmetric XOR Games}}, booktitle = {8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)}, pages = {146--156}, 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.146}, URN = {urn:nbn:de:0030-drops-43156}, doi = {10.4230/LIPIcs.TQC.2013.146}, annote = {Keywords: Random Symmetric XOR games, Entanglement} }
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} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 636-647, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{ambainis:LIPIcs.STACS.2012.636, author = {Ambainis, Andris}, title = {{Variable time amplitude amplification and quantum algorithms for linear algebra problems}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {636--647}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph 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.2012.636}, URN = {urn:nbn:de:0030-drops-34261}, doi = {10.4230/LIPIcs.STACS.2012.636}, annote = {Keywords: quantum computing, quantum algorithms, amplitude amplification, linear equations} }
Feedback for Dagstuhl Publishing