Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3, author = {Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.}, title = {{Optimal Algorithms for Learning Quantum Phase States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {3:1--3:24}, 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.3}, URN = {urn:nbn:de:0030-drops-183139}, doi = {10.4230/LIPIcs.TQC.2023.3}, annote = {Keywords: Tomography, binary phase states, generalized phase states, IQP circuits} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Ramita Maharjan and Thomas Watson. Complexity of Fault Tolerant Query Complexity. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 26:1-26:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{maharjan_et_al:LIPIcs.FSTTCS.2022.26, author = {Maharjan, Ramita and Watson, Thomas}, title = {{Complexity of Fault Tolerant Query Complexity}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {26:1--26:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.26}, URN = {urn:nbn:de:0030-drops-174185}, doi = {10.4230/LIPIcs.FSTTCS.2022.26}, annote = {Keywords: Fault, Tolerant, Query, Complexity} }
Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman. The Parametrized Complexity of Quantum Verification. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 3:1-3:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{arunachalam_et_al:LIPIcs.TQC.2022.3, author = {Arunachalam, Srinivasan and Bravyi, Sergey and Nirkhe, Chinmay and O'Gorman, Bryan}, title = {{The Parametrized Complexity of Quantum Verification}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {3:1--3:18}, 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.3}, URN = {urn:nbn:de:0030-drops-165104}, doi = {10.4230/LIPIcs.TQC.2022.3}, annote = {Keywords: parametrized complexity, quantum verification, QMA} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Md Lutfar Rahman and Thomas Watson. Erdős-Selfridge Theorem for Nonmonotone CNFs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 31:1-31:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{rahman_et_al:LIPIcs.SWAT.2022.31, author = {Rahman, Md Lutfar and Watson, Thomas}, title = {{Erd\H{o}s-Selfridge Theorem for Nonmonotone CNFs}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {31:1--31:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.31}, URN = {urn:nbn:de:0030-drops-161916}, doi = {10.4230/LIPIcs.SWAT.2022.31}, annote = {Keywords: Game, nonmonotone, CNFs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Mika Göös and Gilbert Maystre. A Majority Lemma for Randomised Query Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 18:1-18:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goos_et_al:LIPIcs.CCC.2021.18, author = {G\"{o}\"{o}s, Mika and Maystre, Gilbert}, title = {{A Majority Lemma for Randomised Query Complexity}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {18:1--18:15}, 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.18}, URN = {urn:nbn:de:0030-drops-142922}, doi = {10.4230/LIPIcs.CCC.2021.18}, annote = {Keywords: Query Complexity, Composition, Majority} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Md Lutfar Rahman and Thomas Watson. 6-Uniform Maker-Breaker Game Is PSPACE-Complete. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 57:1-57:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rahman_et_al:LIPIcs.STACS.2021.57, author = {Rahman, Md Lutfar and Watson, Thomas}, title = {{6-Uniform Maker-Breaker Game Is PSPACE-Complete}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {57:1--57:15}, 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.57}, URN = {urn:nbn:de:0030-drops-137020}, doi = {10.4230/LIPIcs.STACS.2021.57}, annote = {Keywords: Game, Maker-Breaker, Complexity, Reduction, PSPACE-complete, NL-hard} }
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 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Toniann Pitassi, Morgan Shirley, and Thomas Watson. Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 92:1-92:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{pitassi_et_al:LIPIcs.ICALP.2020.92, author = {Pitassi, Toniann and Shirley, Morgan and Watson, Thomas}, title = {{Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {92:1--92:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.92}, URN = {urn:nbn:de:0030-drops-124992}, doi = {10.4230/LIPIcs.ICALP.2020.92}, annote = {Keywords: Boolean hierarchies, lifting theorems, query complexity} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Ronitt Rubinfeld and Arsen Vasilyan. Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 28:1-28:34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{rubinfeld_et_al:LIPIcs.ITCS.2020.28, author = {Rubinfeld, Ronitt and Vasilyan, Arsen}, title = {{Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {28:1--28:34}, 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.28}, URN = {urn:nbn:de:0030-drops-117138}, doi = {10.4230/LIPIcs.ITCS.2020.28}, annote = {Keywords: Learning distributions, monotone probability distributions, estimating support size} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Maryam Aliakbarpour and Sandeep Silwal. Testing Properties of Multiple Distributions with Few Samples. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 69:1-69:41, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{aliakbarpour_et_al:LIPIcs.ITCS.2020.69, author = {Aliakbarpour, Maryam and Silwal, Sandeep}, title = {{Testing Properties of Multiple Distributions with Few Samples}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {69:1--69:41}, 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.69}, URN = {urn:nbn:de:0030-drops-117545}, doi = {10.4230/LIPIcs.ITCS.2020.69}, annote = {Keywords: Hypothesis Testing, Property Testing, Distribution Testing, Identity Testing, Closeness Testing, Multiple Sources} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Mika Göös and Thomas Watson. A Lower Bound for Sampling Disjoint Sets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 51:1-51:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2019.51, author = {G\"{o}\"{o}s, Mika and Watson, Thomas}, title = {{A Lower Bound for Sampling Disjoint Sets}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {51:1--51:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.51}, URN = {urn:nbn:de:0030-drops-112666}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.51}, annote = {Keywords: Communication complexity, set disjointness, sampling} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Thomas Watson. Amplification with One NP Oracle Query. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 96:1-96:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{watson:LIPIcs.ICALP.2019.96, author = {Watson, Thomas}, title = {{Amplification with One NP Oracle Query}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {96:1--96:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.96}, URN = {urn:nbn:de:0030-drops-106726}, doi = {10.4230/LIPIcs.ICALP.2019.96}, annote = {Keywords: Amplification, NP, oracle, query} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Thomas Watson. A ZPP^NP[1] Lifting Theorem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 59:1-59:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{watson:LIPIcs.STACS.2019.59, author = {Watson, Thomas}, title = {{A ZPP^NP\lbrack1\rbrack Lifting Theorem}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {59:1--59:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.59}, URN = {urn:nbn:de:0030-drops-102989}, doi = {10.4230/LIPIcs.STACS.2019.59}, annote = {Keywords: Query complexity, communication complexity, lifting} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{rahman_et_al:LIPIcs.ISAAC.2018.9, author = {Rahman, Md Lutfar and Watson, Thomas}, title = {{Complexity of Unordered CNF Games}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {9:1--9:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.9}, URN = {urn:nbn:de:0030-drops-99574}, doi = {10.4230/LIPIcs.ISAAC.2018.9}, annote = {Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time} }
Feedback for Dagstuhl Publishing