Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
William M. Hoza. A Technique for Hardness Amplification Against AC⁰. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hoza:LIPIcs.CCC.2024.1, author = {Hoza, William M.}, title = {{A Technique for Hardness Amplification Against AC⁰}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {1:1--1:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.1}, URN = {urn:nbn:de:0030-drops-203977}, doi = {10.4230/LIPIcs.CCC.2024.1}, annote = {Keywords: Bounded-depth circuits, average-case lower bounds, hardness amplification, XOR lemmas} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan. A Strong Direct Sum Theorem for Distributional Query Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 16:1-16:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blanc_et_al:LIPIcs.CCC.2024.16, author = {Blanc, Guy and Koch, Caleb and Strassle, Carmen and Tan, Li-Yang}, title = {{A Strong Direct Sum Theorem for Distributional Query Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {16:1--16:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.16}, URN = {urn:nbn:de:0030-drops-204123}, doi = {10.4230/LIPIcs.CCC.2024.16}, annote = {Keywords: Query complexity, direct product theorem, hardcore theorem} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bassirian_et_al:LIPIcs.TQC.2023.11, author = {Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal}, title = {{On the Power of Nonstandard Quantum Oracles}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {11:1--11:25}, 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.11}, URN = {urn:nbn:de:0030-drops-183215}, doi = {10.4230/LIPIcs.TQC.2023.11}, annote = {Keywords: quantum complexity, QCMA, expander graphs, representation theory} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Anand Natarajan and Chinmay Nirkhe. A Distribution Testing Oracle Separating QMA and QCMA. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{natarajan_et_al:LIPIcs.CCC.2023.22, author = {Natarajan, Anand and Nirkhe, Chinmay}, title = {{A Distribution Testing Oracle Separating QMA and QCMA}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {22:1--22:27}, 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.22}, URN = {urn:nbn:de:0030-drops-182928}, doi = {10.4230/LIPIcs.CCC.2023.22}, annote = {Keywords: quantum non-determinism, complexity theory} }
Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman. Memory Compression with Quantum Random-Access Gates. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{buhrman_et_al:LIPIcs.TQC.2022.10, author = {Buhrman, Harry and Loff, Bruno and Patro, Subhasree and Speelman, Florian}, title = {{Memory Compression with Quantum Random-Access Gates}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {10:1--10:19}, 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.10}, URN = {urn:nbn:de:0030-drops-165177}, doi = {10.4230/LIPIcs.TQC.2022.10}, annote = {Keywords: complexity theory, data structures, algorithms, quantum walk} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 30:1-30:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{anshu_et_al:LIPIcs.CCC.2021.30, author = {Anshu, Anurag and Ben-David, Shalev and Kundu, Srijita}, title = {{On Query-To-Communication Lifting for Adversary Bounds}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {30:1--30:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30}, URN = {urn:nbn:de:0030-drops-143042}, doi = {10.4230/LIPIcs.CCC.2021.30}, annote = {Keywords: Quantum computing, query complexity, communication complexity, lifting theorems, adversary method} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Andrew M. Childs, Shih-Han Hung, and Tongyang Li. Quantum Query Complexity with Matrix-Vector Products. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{childs_et_al:LIPIcs.ICALP.2021.55, author = {Childs, Andrew M. and Hung, Shih-Han and Li, Tongyang}, title = {{Quantum Query Complexity with Matrix-Vector Products}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.55}, URN = {urn:nbn:de:0030-drops-141242}, doi = {10.4230/LIPIcs.ICALP.2021.55}, annote = {Keywords: Quantum algorithms, quantum query complexity, matrix-vector products} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
William Kretschmer. The Quantum Supremacy Tsirelson Inequality. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kretschmer:LIPIcs.ITCS.2021.13, author = {Kretschmer, William}, title = {{The Quantum Supremacy Tsirelson Inequality}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.13}, URN = {urn:nbn:de:0030-drops-135524}, doi = {10.4230/LIPIcs.ITCS.2021.13}, annote = {Keywords: quantum supremacy, quantum query complexity, random circuit sampling} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{garg_et_al:LIPIcs.ITCS.2021.53, author = {Garg, Ankit and Kothari, Robin and Netrapalli, Praneeth and Sherif, Suhail}, title = {{No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {53:1--53:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.53}, URN = {urn:nbn:de:0030-drops-135921}, doi = {10.4230/LIPIcs.ITCS.2021.53}, annote = {Keywords: Quantum algorithms, Gradient descent, Convex optimization} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Filmus, Or Meir, and Avishay Tal. Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 89:1-89:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2021.89, author = {Filmus, Yuval and Meir, Or and Tal, Avishay}, title = {{Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {89:1--89:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.89}, URN = {urn:nbn:de:0030-drops-136281}, doi = {10.4230/LIPIcs.ITCS.2021.89}, annote = {Keywords: De Morgan formulas, KRW Conjecture, shrinkage, random restrictions, random projections, bounded depth circuits, constant depth circuits, formula complexity} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson. When Is Amplification Necessary for Composition in Randomized Query Complexity?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bendavid_et_al:LIPIcs.APPROX/RANDOM.2020.28, author = {Ben-David, Shalev and G\"{o}\"{o}s, Mika and Kothari, Robin and Watson, Thomas}, title = {{When Is Amplification Necessary for Composition in Randomized Query Complexity?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.28}, URN = {urn:nbn:de:0030-drops-126316}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.28}, annote = {Keywords: Amplification, composition, query complexity} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 7:1-7:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2020.7, author = {Aaronson, Scott and Kothari, Robin and Kretschmer, William and Thaler, Justin}, title = {{Quantum Lower Bounds for Approximate Counting via Laurent Polynomials}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {7:1--7:47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.7}, URN = {urn:nbn:de:0030-drops-125593}, doi = {10.4230/LIPIcs.CCC.2020.7}, annote = {Keywords: Approximate counting, Laurent polynomials, QSampling, query complexity} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Nikhil S. Mande, Justin Thaler, and Shuchen Zhu. Improved Approximate Degree Bounds for k-Distinctness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{mande_et_al:LIPIcs.TQC.2020.2, author = {Mande, Nikhil S. and Thaler, Justin and Zhu, Shuchen}, title = {{Improved Approximate Degree Bounds for k-Distinctness}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {2:1--2:22}, 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.2}, URN = {urn:nbn:de:0030-drops-120613}, doi = {10.4230/LIPIcs.TQC.2020.2}, annote = {Keywords: Quantum Query Complexity, Approximate Degree, Dual Polynomials, k-distinctness} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arunachalam_et_al:LIPIcs.TQC.2020.10, author = {Arunachalam, Srinivasan and Belovs, Aleksandrs and Childs, Andrew M. and Kothari, Robin and Rosmanis, Ansis and de Wolf, Ronald}, title = {{Quantum Coupon Collector}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {10:1--10:17}, 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.10}, URN = {urn:nbn:de:0030-drops-120692}, doi = {10.4230/LIPIcs.TQC.2020.10}, annote = {Keywords: Quantum algorithms, Adversary method, Coupon collector, Quantum learning theory} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Stacey Jeffery. Span Programs and Quantum Space Complexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 4:1-4:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jeffery:LIPIcs.ITCS.2020.4, author = {Jeffery, Stacey}, title = {{Span Programs and Quantum Space Complexity}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {4:1--4: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.4}, URN = {urn:nbn:de:0030-drops-116896}, doi = {10.4230/LIPIcs.ITCS.2020.4}, annote = {Keywords: Quantum space complexity, span programs} }