Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Ziyi Guan, Yunqi Huang, Penghui Yao, and Zekun Ye. Quantum and Classical Communication Complexity of Permutation-Invariant Functions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guan_et_al:LIPIcs.STACS.2024.39, author = {Guan, Ziyi and Huang, Yunqi and Yao, Penghui and Ye, Zekun}, title = {{Quantum and Classical Communication Complexity of Permutation-Invariant Functions}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {39:1--39:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.39}, URN = {urn:nbn:de:0030-drops-197498}, doi = {10.4230/LIPIcs.STACS.2024.39}, annote = {Keywords: Communication complexity, Permutation-invariant functions, Log-rank Conjecture, Quantum advantages} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational Problem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.1, author = {Aaronson, Scott and Buhrman, Harry and Kretschmer, William}, title = {{A Qubit, a Coin, and an Advice String Walk into a Relational Problem}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {1:1--1:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.1}, URN = {urn:nbn:de:0030-drops-195290}, doi = {10.4230/LIPIcs.ITCS.2024.1}, annote = {Keywords: Relational problems, quantum advice, randomized advice, FBQP, FBPP} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum Pseudoentanglement. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.2, author = {Aaronson, Scott and Bouland, Adam and Fefferman, Bill and Ghosh, Soumik and Vazirani, Umesh and Zhang, Chenyi and Zhou, Zixin}, title = {{Quantum Pseudoentanglement}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.2}, URN = {urn:nbn:de:0030-drops-195300}, doi = {10.4230/LIPIcs.ITCS.2024.2}, annote = {Keywords: Quantum computing, Quantum complexity theory, entanglement} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jiawei Li. Total NP Search Problems with Abundant Solutions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li:LIPIcs.ITCS.2024.75, author = {Li, Jiawei}, title = {{Total NP Search Problems with Abundant Solutions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {75:1--75:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.75}, URN = {urn:nbn:de:0030-drops-196031}, doi = {10.4230/LIPIcs.ITCS.2024.75}, annote = {Keywords: TFNP, Pigeonhole Principle} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Adam Bene Watts and John Bostanci. Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 97:1-97:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{watts_et_al:LIPIcs.ITCS.2024.97, author = {Watts, Adam Bene and Bostanci, John}, title = {{Quantum Event Learning and Gentle Random Measurements}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {97:1--97:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.97}, URN = {urn:nbn:de:0030-drops-196254}, doi = {10.4230/LIPIcs.ITCS.2024.97}, annote = {Keywords: Event learning, gentle measurments, random measurements, quantum or, threshold search, shadow tomography} }
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-dev.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)
Scott Aaronson and Sabee Grewal. Efficient Tomography of Non-Interacting-Fermion States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{aaronson_et_al:LIPIcs.TQC.2023.12, author = {Aaronson, Scott and Grewal, Sabee}, title = {{Efficient Tomography of Non-Interacting-Fermion States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {12:1--12: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.12}, URN = {urn:nbn:de:0030-drops-183222}, doi = {10.4230/LIPIcs.TQC.2023.12}, annote = {Keywords: free-fermions, Gaussian fermions, non-interacting fermions, quantum state tomography, efficient tomography} }
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-dev.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 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{brakerski_et_al:LIPIcs.ITCS.2023.24, author = {Brakerski, Zvika and Canetti, Ran and Qian, Luowen}, title = {{On the Computational Hardness Needed for Quantum Cryptography}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {24:1--24:21}, 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.24}, URN = {urn:nbn:de:0030-drops-175278}, doi = {10.4230/LIPIcs.ITCS.2023.24}, annote = {Keywords: quantum cryptography, efi, commitment scheme, oblivious transfer, zero knowledge, secure multiparty computation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{grewal_et_al:LIPIcs.ITCS.2023.64, author = {Grewal, Sabee and Iyer, Vishnu and Kretschmer, William and Liang, Daniel}, title = {{Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {64:1--64:20}, 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.64}, URN = {urn:nbn:de:0030-drops-175670}, doi = {10.4230/LIPIcs.ITCS.2023.64}, annote = {Keywords: Pseudorandom quantum states, Clifford + T, Haar random, Bell sampling, stabilizer formalism, stabilizer extent, stabilizer fidelity, learning theory, complexity theory} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Zhao Song and Ruizhe Zhang. Hyperbolic Concentration, Anti-Concentration, and Discrepancy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{song_et_al:LIPIcs.APPROX/RANDOM.2022.10, author = {Song, Zhao and Zhang, Ruizhe}, title = {{Hyperbolic Concentration, Anti-Concentration, and Discrepancy}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {10:1--10:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.10}, URN = {urn:nbn:de:0030-drops-171324}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.10}, annote = {Keywords: Hyperbolic polynomial, Chernoff bound, Concentration, Discrepancy theory, Anti-concentration} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Scott Aaronson, DeVon Ingram, and William Kretschmer. The Acrobatics of BQP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2022.20, author = {Aaronson, Scott and Ingram, DeVon and Kretschmer, William}, title = {{The Acrobatics of BQP}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.20}, URN = {urn:nbn:de:0030-drops-165820}, doi = {10.4230/LIPIcs.CCC.2022.20}, annote = {Keywords: BQP, Forrelation, oracle separations, Polynomial Hierarchy, query complexity} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.CCC.2022.28, author = {Bansal, Nikhil and Sinha, Makrand and de Wolf, Ronald}, title = {{Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {28:1--28:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.28}, URN = {urn:nbn:de:0030-drops-165908}, doi = {10.4230/LIPIcs.CCC.2022.28}, annote = {Keywords: Aaronson-Ambainis conjecture, Quantum query complexity, Classical query complexity, Free probability, Completely bounded norm, Analysis of Boolean functions, Influence} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chia_et_al:LIPIcs.ITCS.2022.47, author = {Chia, Nai-Hui and Chou, Chi-Ning and Zhang, Jiayu and Zhang, Ruizhe}, title = {{Quantum Meets the Minimum Circuit Size Problem}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {47:1--47:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.47}, URN = {urn:nbn:de:0030-drops-156433}, doi = {10.4230/LIPIcs.ITCS.2022.47}, annote = {Keywords: Quantum Computation, Quantum Complexity, Minimum Circuit Size Problem} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Scott Aaronson. BQP After 28 Years (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{aaronson:LIPIcs.FSTTCS.2021.1, author = {Aaronson, Scott}, title = {{BQP After 28 Years}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.1}, URN = {urn:nbn:de:0030-drops-155124}, doi = {10.4230/LIPIcs.FSTTCS.2021.1}, annote = {Keywords: quantum computing, complexity theory, oracle separations, circuit lower bounds} }
Feedback for Dagstuhl Publishing