Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Robin Kothari
@article{DBLP:journals/siamcomp/HaahHKL23,
author = {Jeongwan Haah and
Matthew B. Hastings and
Robin Kothari and
Guang Hao Low},
title = {Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians},
journal = {{SIAM} J. Comput.},
volume = {52},
number = {6},
pages = {S18--250},
year = {2023},
url = {https://doi.org/10.1137/18m1231511},
doi = {10.1137/18M1231511},
timestamp = {Fri, 26 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/HaahHKL23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaahKOT23,
author = {Jeongwan Haah and
Robin Kothari and
Ryan O'Donnell and
Ewin Tang},
title = {Query-optimal estimation of unitary channels in diamond distance},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {363--390},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00028},
doi = {10.1109/FOCS57990.2023.00028},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/HaahKOT23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BabbushBKSW23,
author = {Ryan Babbush and
Dominic W. Berry and
Robin Kothari and
Rolando D. Somma and
Nathan Wiebe},
title = {Exponential quantum speedup in simulating coupled classical oscillators\({}^{\mbox{*}}\)},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {405--414},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00030},
doi = {10.1109/FOCS57990.2023.00030},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BabbushBKSW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KothariO23,
author = {Robin Kothari and
Ryan O'Donnell},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {Mean estimation when you have the source code; or, quantum Monte Carlo
methods},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {1186--1215},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch44},
doi = {10.1137/1.9781611977554.CH44},
timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
biburl = {https://dblp.org/rec/conf/soda/KothariO23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2302-14066,
author = {Jeongwan Haah and
Robin Kothari and
Ryan O'Donnell and
Ewin Tang},
title = {Query-optimal estimation of unitary channels in diamond distance},
journal = {CoRR},
volume = {abs/2302.14066},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2302.14066},
doi = {10.48550/ARXIV.2302.14066},
eprinttype = {arXiv},
eprint = {2302.14066},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2302-14066.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaahKT22,
author = {Jeongwan Haah and
Robin Kothari and
Ewin Tang},
title = {Optimal learning of quantum Hamiltonians from high-temperature Gibbs
states},
booktitle = {63rd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2022, Denver, CO, USA, October 31 - November 3, 2022},
pages = {135--146},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS54457.2022.00020},
doi = {10.1109/FOCS54457.2022.00020},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/HaahKT22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2208-07544,
author = {Robin Kothari and
Ryan O'Donnell},
title = {Mean estimation when you have the source code; or, quantum Monte Carlo
methods},
journal = {CoRR},
volume = {abs/2208.07544},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2208.07544},
doi = {10.48550/ARXIV.2208.07544},
eprinttype = {arXiv},
eprint = {2208.07544},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2208-07544.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2210-06419,
author = {Andrew M. Childs and
Robin Kothari and
Matt Kovacs{-}Deak and
Aarthi Sundaram and
Daochen Wang},
title = {Quantum divide and conquer},
journal = {CoRR},
volume = {abs/2210.06419},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2210.06419},
doi = {10.48550/ARXIV.2210.06419},
eprinttype = {arXiv},
eprint = {2210.06419},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2210-06419.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/quantum/BunKT21,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {Quantum algorithms and approximating polynomials for composed functions
with shared inputs},
journal = {Quantum},
volume = {5},
pages = {543},
year = {2021},
url = {https://doi.org/10.22331/q-2021-09-16-543},
doi = {10.22331/Q-2021-09-16-543},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/quantum/BunKT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BalodisBG0K21,
author = {Kaspars Balodis and
Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Siddhartha Jain and
Robin Kothari},
title = {Unambiguous DNFs and Alon-Saks-Seymour},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {116--124},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00020},
doi = {10.1109/FOCS52979.2021.00020},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BalodisBG0K21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/WangSKKR21,
author = {Daochen Wang and
Aarthi Sundaram and
Robin Kothari and
Ashish Kapoor and
Martin Roetteler},
editor = {Marina Meila and
Tong Zhang},
title = {Quantum algorithms for reinforcement learning with a generative model},
booktitle = {Proceedings of the 38th International Conference on Machine Learning,
{ICML} 2021, 18-24 July 2021, Virtual Event},
series = {Proceedings of Machine Learning Research},
volume = {139},
pages = {10916--10926},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v139/wang21w.html},
timestamp = {Wed, 25 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icml/WangSKKR21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/GargKNS21,
author = {Ankit Garg and
Robin Kothari and
Praneeth Netrapalli and
Suhail Sherif},
editor = {James R. Lee},
title = {No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization},
booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
2021, January 6-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {185},
pages = {53:1--53:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.53},
doi = {10.4230/LIPICS.ITCS.2021.53},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/GargKNS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/GargKNS21,
author = {Ankit Garg and
Robin Kothari and
Praneeth Netrapalli and
Suhail Sherif},
editor = {Marc'Aurelio Ranzato and
Alina Beygelzimer and
Yann N. Dauphin and
Percy Liang and
Jennifer Wortman Vaughan},
title = {Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness},
booktitle = {Advances in Neural Information Processing Systems 34: Annual Conference
on Neural Information Processing Systems 2021, NeurIPS 2021, December
6-14, 2021, virtual},
pages = {29874--29884},
year = {2021},
url = {https://proceedings.neurips.cc/paper/2021/hash/fa6c94460e902005a0b660266190c8ba-Abstract.html},
timestamp = {Tue, 03 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/nips/GargKNS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AaronsonBKRT21,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari and
Shravas Rao and
Avishay Tal},
editor = {Samir Khuller and
Virginia Vassilevska Williams},
title = {Degree vs. approximate degree and Quantum implications of Huang's
sensitivity theorem},
booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Virtual Event, Italy, June 21-25, 2021},
pages = {1330--1342},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3406325.3451047},
doi = {10.1145/3406325.3451047},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AaronsonBKRT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2102-08348,
author = {Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Siddhartha Jain and
Robin Kothari},
title = {Unambiguous DNFs from Hex},
journal = {CoRR},
volume = {abs/2102.08348},
year = {2021},
url = {https://arxiv.org/abs/2102.08348},
eprinttype = {arXiv},
eprint = {2102.08348},
timestamp = {Sun, 21 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2102-08348.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2108-04842,
author = {Jeongwan Haah and
Robin Kothari and
Ewin Tang},
title = {Optimal learning of quantum Hamiltonians from high-temperature Gibbs
states},
journal = {CoRR},
volume = {abs/2108.04842},
year = {2021},
url = {https://arxiv.org/abs/2108.04842},
eprinttype = {arXiv},
eprint = {2108.04842},
timestamp = {Fri, 20 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2108-04842.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-01118,
author = {Ankit Garg and
Robin Kothari and
Praneeth Netrapalli and
Suhail Sherif},
title = {Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness},
journal = {CoRR},
volume = {abs/2112.01118},
year = {2021},
url = {https://arxiv.org/abs/2112.01118},
eprinttype = {arXiv},
eprint = {2112.01118},
timestamp = {Wed, 08 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-01118.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-08451,
author = {Daochen Wang and
Aarthi Sundaram and
Robin Kothari and
Ashish Kapoor and
Martin Roetteler},
title = {Quantum Algorithms for Reinforcement Learning with a Generative Model},
journal = {CoRR},
volume = {abs/2112.08451},
year = {2021},
url = {https://arxiv.org/abs/2112.08451},
eprinttype = {arXiv},
eprint = {2112.08451},
timestamp = {Wed, 05 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-08451.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-DavidGJK21,
author = {Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Siddhartha Jain and
Robin Kothari},
title = {Unambiguous DNFs from Hex},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR21-016}},
year = {2021},
url = {https://eccc.weizmann.ac.il/report/2021/016},
eprinttype = {ECCC},
eprint = {TR21-016},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-DavidGJK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/BunKT20,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via
Dual Polynomials},
journal = {Theory Comput.},
volume = {16},
pages = {1--71},
year = {2020},
url = {https://doi.org/10.4086/toc.2020.v016a010},
doi = {10.4086/TOC.2020.V016A010},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/BunKT20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Ben-DavidGK020,
author = {Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Robin Kothari and
Thomas Watson},
editor = {Jaroslaw Byrka and
Raghu Meka},
title = {When Is Amplification Necessary for Composition in Randomized Query
Complexity?},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2020, August 17-19, 2020, Virtual
Conference},
series = {LIPIcs},
volume = {176},
pages = {28:1--28:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.28},
doi = {10.4230/LIPICS.APPROX/RANDOM.2020.28},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/Ben-DavidGK020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AaronsonKKT20,
author = {Scott Aaronson and
Robin Kothari and
William Kretschmer and
Justin Thaler},
editor = {Shubhangi Saraf},
title = {Quantum Lower Bounds for Approximate Counting via Laurent Polynomials},
booktitle = {35th Computational Complexity Conference, {CCC} 2020, July 28-31,
2020, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
series = {LIPIcs},
volume = {169},
pages = {7:1--7:47},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.CCC.2020.7},
doi = {10.4230/LIPICS.CCC.2020.7},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/AaronsonKKT20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/ArunachalamBCKR20,
author = {Srinivasan Arunachalam and
Aleksandrs Belovs and
Andrew M. Childs and
Robin Kothari and
Ansis Rosmanis and
Ronald de Wolf},
editor = {Steven T. Flammia},
title = {Quantum Coupon Collector},
booktitle = {15th Conference on the Theory of Quantum Computation, Communication
and Cryptography, {TQC} 2020, June 9-12, 2020, Riga, Latvia},
series = {LIPIcs},
volume = {158},
pages = {10:1--10:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.TQC.2020.10},
doi = {10.4230/LIPICS.TQC.2020.10},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tqc/ArunachalamBCKR20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-07688,
author = {Srinivasan Arunachalam and
Aleksandrs Belovs and
Andrew M. Childs and
Robin Kothari and
Ansis Rosmanis and
Ronald de Wolf},
title = {Quantum Coupon Collector},
journal = {CoRR},
volume = {abs/2002.07688},
year = {2020},
url = {https://arxiv.org/abs/2002.07688},
eprinttype = {arXiv},
eprint = {2002.07688},
timestamp = {Tue, 03 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-07688.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2004-13231,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari and
Avishay Tal},
title = {Quantum Implications of Huang's Sensitivity Theorem},
journal = {CoRR},
volume = {abs/2004.13231},
year = {2020},
url = {https://arxiv.org/abs/2004.13231},
eprinttype = {arXiv},
eprint = {2004.13231},
timestamp = {Sun, 03 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2004-13231.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2006-10957,
author = {Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Robin Kothari and
Thomas Watson},
title = {When Is Amplification Necessary for Composition in Randomized Query
Complexity?},
journal = {CoRR},
volume = {abs/2006.10957},
year = {2020},
url = {https://arxiv.org/abs/2006.10957},
eprinttype = {arXiv},
eprint = {2006.10957},
timestamp = {Tue, 23 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2006-10957.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-01801,
author = {Ankit Garg and
Robin Kothari and
Praneeth Netrapalli and
Suhail Sherif},
title = {No quantum speedup over gradient descent for non-smooth convex optimization},
journal = {CoRR},
volume = {abs/2010.01801},
year = {2020},
url = {https://arxiv.org/abs/2010.01801},
eprinttype = {arXiv},
eprint = {2010.01801},
timestamp = {Mon, 12 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-01801.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-12629,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari and
Shravas Rao and
Avishay Tal},
title = {Degree vs. Approximate Degree and Quantum Implications of Huang's
Sensitivity Theorem},
journal = {CoRR},
volume = {abs/2010.12629},
year = {2020},
url = {https://arxiv.org/abs/2010.12629},
eprinttype = {arXiv},
eprint = {2010.12629},
timestamp = {Tue, 03 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-12629.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AaronsonBKT20,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari and
Avishay Tal},
title = {Quantum Implications of Huang's Sensitivity Theorem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-066}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/066},
eprinttype = {ECCC},
eprint = {TR20-066},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonBKT20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BunKT19,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
editor = {Timothy M. Chan},
title = {Quantum algorithms and approximating polynomials for composed functions
with shared inputs},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {662--678},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.42},
doi = {10.1137/1.9781611975482.42},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/BunKT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/WattsKST19,
author = {Adam Bene Watts and
Robin Kothari and
Luke Schaeffer and
Avishay Tal},
editor = {Moses Charikar and
Edith Cohen},
title = {Exponential separation between shallow quantum circuits and unbounded
fan-in shallow classical circuits},
booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019},
pages = {515--526},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3313276.3316404},
doi = {10.1145/3313276.3316404},
timestamp = {Mon, 15 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/WattsKST19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/Ben-DavidK19,
author = {Shalev Ben{-}David and
Robin Kothari},
editor = {Wim van Dam and
Laura Mancinska},
title = {Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical
Zero Knowledge},
booktitle = {14th Conference on the Theory of Quantum Computation, Communication
and Cryptography, {TQC} 2019, June 3-5, 2019, University of Maryland,
College Park, Maryland, {USA}},
series = {LIPIcs},
volume = {135},
pages = {2:1--2:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.TQC.2019.2},
doi = {10.4230/LIPICS.TQC.2019.2},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/tqc/Ben-DavidK19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1902-03660,
author = {Shalev Ben{-}David and
Robin Kothari},
title = {Quantum distinguishing complexity, zero-error algorithms, and statistical
zero knowledge},
journal = {CoRR},
volume = {abs/1902.03660},
year = {2019},
url = {http://arxiv.org/abs/1902.03660},
eprinttype = {arXiv},
eprint = {1902.03660},
timestamp = {Tue, 21 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1902-03660.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-08914,
author = {Scott Aaronson and
Robin Kothari and
William Kretschmer and
Justin Thaler},
title = {Quantum Lower Bounds for Approximate Counting via Laurent Polynomials},
journal = {CoRR},
volume = {abs/1904.08914},
year = {2019},
url = {http://arxiv.org/abs/1904.08914},
eprinttype = {arXiv},
eprint = {1904.08914},
timestamp = {Sat, 27 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-08914.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1906-08890,
author = {Adam Bene Watts and
Robin Kothari and
Luke Schaeffer and
Avishay Tal},
title = {Exponential separation between shallow quantum circuits and unbounded
fan-in shallow classical circuits},
journal = {CoRR},
volume = {abs/1906.08890},
year = {2019},
url = {http://arxiv.org/abs/1906.08890},
eprinttype = {arXiv},
eprint = {1906.08890},
timestamp = {Mon, 24 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1906-08890.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AaronsonKKT19,
author = {Scott Aaronson and
Robin Kothari and
William Kretschmer and
Justin Thaler},
title = {Quantum Lower Bounds for Approximate Counting via Laurent Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-062}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/062},
eprinttype = {ECCC},
eprint = {TR19-062},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonKKT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/WattsKST19,
author = {Adam Bene Watts and
Robin Kothari and
Luke Schaeffer and
Avishay Tal},
title = {Exponential separation between shallow quantum circuits and unbounded
fan-in shallow classical circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-089}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/089},
eprinttype = {ECCC},
eprint = {TR19-089},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/WattsKST19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Ben-DavidK18,
author = {Shalev Ben{-}David and
Robin Kothari},
title = {Randomized Query Complexity of Sabotaged and Composed Functions},
journal = {Theory Comput.},
volume = {14},
number = {1},
pages = {1--27},
year = {2018},
url = {https://doi.org/10.4086/toc.2018.v014a005},
doi = {10.4086/TOC.2018.V014A005},
timestamp = {Mon, 26 Oct 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/Ben-DavidK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ben-DavidBGK18,
author = {Shalev Ben{-}David and
Adam Bouland and
Ankit Garg and
Robin Kothari},
editor = {Mikkel Thorup},
title = {Classical Lower Bounds from Quantum Upper Bounds},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {339--349},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00040},
doi = {10.1109/FOCS.2018.00040},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ben-DavidBGK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaahHKL18,
author = {Jeongwan Haah and
Matthew B. Hastings and
Robin Kothari and
Guang Hao Low},
editor = {Mikkel Thorup},
title = {Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {350--360},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00041},
doi = {10.1109/FOCS.2018.00041},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HaahHKL18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BunKT18,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {The polynomial method strikes back: tight quantum query bounds via
dual polynomials},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {297--310},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188784},
doi = {10.1145/3188745.3188784},
timestamp = {Mon, 15 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BunKT18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1807-06256,
author = {Shalev Ben{-}David and
Adam Bouland and
Ankit Garg and
Robin Kothari},
title = {Classical lower bounds from quantum upper bounds},
journal = {CoRR},
volume = {abs/1807.06256},
year = {2018},
url = {http://arxiv.org/abs/1807.06256},
eprinttype = {arXiv},
eprint = {1807.06256},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1807-06256.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1809-02254,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {Quantum algorithms and approximating polynomials for composed functions
with shared inputs},
journal = {CoRR},
volume = {abs/1809.02254},
year = {2018},
url = {http://arxiv.org/abs/1809.02254},
eprinttype = {arXiv},
eprint = {1809.02254},
timestamp = {Fri, 05 Oct 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1809-02254.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BunKT18,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {Quantum algorithms and approximating polynomials for composed functions
with shared inputs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-156}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/156},
eprinttype = {ECCC},
eprint = {TR18-156},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BunKT18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChildsKS17,
author = {Andrew M. Childs and
Robin Kothari and
Rolando D. Somma},
title = {Quantum Algorithm for Systems of Linear Equations with Exponentially
Improved Dependence on Precision},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {6},
pages = {1920--1950},
year = {2017},
url = {https://doi.org/10.1137/16M1087072},
doi = {10.1137/16M1087072},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChildsKS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AnshuBGJKL17,
author = {Anurag Anshu and
Shalev Ben{-}David and
Ankit Garg and
Rahul Jain and
Robin Kothari and
Troy Lee},
editor = {Ryan O'Donnell},
title = {Separating Quantum Communication and Approximate Rank},
booktitle = {32nd Computational Complexity Conference, {CCC} 2017, July 6-9, 2017,
Riga, Latvia},
series = {LIPIcs},
volume = {79},
pages = {24:1--24:33},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.CCC.2017.24},
doi = {10.4230/LIPICS.CCC.2017.24},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/AnshuBGJKL17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1710-09079,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via
Dual Polynomials},
journal = {CoRR},
volume = {abs/1710.09079},
year = {2017},
url = {http://arxiv.org/abs/1710.09079},
eprinttype = {arXiv},
eprint = {1710.09079},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1710-09079.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BunKT17,
author = {Mark Bun and
Robin Kothari and
Justin Thaler},
title = {The Polynomial Method Strikes Back: Tight Quantum Query Bounds via
Dual Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-169}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/169},
eprinttype = {ECCC},
eprint = {TR17-169},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BunKT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/JefferyKGM16,
author = {Stacey Jeffery and
Robin Kothari and
Fran{\c{c}}ois Le Gall and
Fr{\'{e}}d{\'{e}}ric Magniez},
title = {Improving Quantum Query Complexity of Boolean Matrix Multiplication
Using Graph Collision},
journal = {Algorithmica},
volume = {76},
number = {1},
pages = {1--16},
year = {2016},
url = {https://doi.org/10.1007/s00453-015-9985-x},
doi = {10.1007/S00453-015-9985-X},
timestamp = {Thu, 15 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/JefferyKGM16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AmbainisKK16,
author = {Andris Ambainis and
Martins Kokainis and
Robin Kothari},
editor = {Ran Raz},
title = {Nearly Optimal Separations Between Communication (or Query) Complexity
and Partitions},
booktitle = {31st Conference on Computational Complexity, {CCC} 2016, May 29 to
June 1, 2016, Tokyo, Japan},
series = {LIPIcs},
volume = {50},
pages = {4:1--4:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.CCC.2016.4},
doi = {10.4230/LIPICS.CCC.2016.4},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/AmbainisKK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AnshuBBG0KLS16,
author = {Anurag Anshu and
Aleksandrs Belovs and
Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Rahul Jain and
Robin Kothari and
Troy Lee and
Miklos Santha},
editor = {Irit Dinur},
title = {Separations in Communication Complexity Using Cheat Sheets and Information
Complexity},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {555--564},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.66},
doi = {10.1109/FOCS.2016.66},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AnshuBBG0KLS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Ben-DavidK16,
author = {Shalev Ben{-}David and
Robin Kothari},
editor = {Ioannis Chatzigiannakis and
Michael Mitzenmacher and
Yuval Rabani and
Davide Sangiorgi},
title = {Randomized Query Complexity of Sabotaged and Composed Functions},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming,
{ICALP} 2016, July 11-15, 2016, Rome, Italy},
series = {LIPIcs},
volume = {55},
pages = {60:1--60:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.60},
doi = {10.4230/LIPICS.ICALP.2016.60},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/Ben-DavidK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AaronsonBK16,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Separations in query complexity using cheat sheets},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {863--876},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897644},
doi = {10.1145/2897518.2897644},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AaronsonBK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/KothariN16,
author = {Robin Kothari and
Ashwin Nayak},
title = {Quantum Algorithms for Matrix Multiplication and Product Verification},
booktitle = {Encyclopedia of Algorithms},
pages = {1673--1677},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_303},
doi = {10.1007/978-1-4939-2864-4\_303},
timestamp = {Mon, 18 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/KothariN16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AnshuBBGJKLS16,
author = {Anurag Anshu and
Aleksandrs Belovs and
Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Rahul Jain and
Robin Kothari and
Troy Lee and
Miklos Santha},
title = {Separations in communication complexity using cheat sheets and information
complexity},
journal = {CoRR},
volume = {abs/1605.01142},
year = {2016},
url = {http://arxiv.org/abs/1605.01142},
eprinttype = {arXiv},
eprint = {1605.01142},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AnshuBBGJKLS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Ben-DavidK16,
author = {Shalev Ben{-}David and
Robin Kothari},
title = {Randomized query complexity of sabotaged and composed functions},
journal = {CoRR},
volume = {abs/1605.09071},
year = {2016},
url = {http://arxiv.org/abs/1605.09071},
eprinttype = {arXiv},
eprint = {1605.09071},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Ben-DavidK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AnshuBG0KL16,
author = {Anurag Anshu and
Shalev Ben{-}David and
Ankit Garg and
Rahul Jain and
Robin Kothari and
Troy Lee},
title = {Separating quantum communication and approximate rank},
journal = {CoRR},
volume = {abs/1611.05754},
year = {2016},
url = {http://arxiv.org/abs/1611.05754},
eprinttype = {arXiv},
eprint = {1611.05754},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AnshuBG0KL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AnshuBBGJKLS16,
author = {Anurag Anshu and
Aleksandrs Belovs and
Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Rahul Jain and
Robin Kothari and
Troy Lee and
Miklos Santha},
title = {Separations in communication complexity using cheat sheets and information
complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-072}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/072},
eprinttype = {ECCC},
eprint = {TR16-072},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AnshuBBGJKLS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Ben-DavidK16,
author = {Shalev Ben{-}David and
Robin Kothari},
title = {Randomized query complexity of sabotaged and composed functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-087}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/087},
eprinttype = {ECCC},
eprint = {TR16-087},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Ben-DavidK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KothariRS15,
author = {Robin Kothari and
David Racicot{-}Desloges and
Miklos Santha},
editor = {Naveen Garg and
Klaus Jansen and
Anup Rao and
Jos{\'{e}} D. P. Rolim},
title = {Separating Decision Tree Complexity from Subcube Partition Complexity},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2015, August 24-26, 2015, Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {40},
pages = {915--930},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.915},
doi = {10.4230/LIPICS.APPROX-RANDOM.2015.915},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/KothariRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BerryCK15,
author = {Dominic W. Berry and
Andrew M. Childs and
Robin Kothari},
editor = {Venkatesan Guruswami},
title = {Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {792--809},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.54},
doi = {10.1109/FOCS.2015.54},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BerryCK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KothariRS15,
author = {Robin Kothari and
David Racicot{-}Desloges and
Miklos Santha},
title = {Separating decision tree complexity from subcube partition complexity},
journal = {CoRR},
volume = {abs/1504.01339},
year = {2015},
url = {http://arxiv.org/abs/1504.01339},
eprinttype = {arXiv},
eprint = {1504.01339},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KothariRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AaronsonBK15,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari},
title = {Separations in query complexity using cheat sheets},
journal = {CoRR},
volume = {abs/1511.01937},
year = {2015},
url = {http://arxiv.org/abs/1511.01937},
eprinttype = {arXiv},
eprint = {1511.01937},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AaronsonBK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Kothari15,
author = {Robin Kothari},
title = {Nearly optimal separations between communication (or query) complexity
and partitions},
journal = {CoRR},
volume = {abs/1512.01210},
year = {2015},
url = {http://arxiv.org/abs/1512.01210},
eprinttype = {arXiv},
eprint = {1512.01210},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Kothari15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AaronsonBK15,
author = {Scott Aaronson and
Shalev Ben{-}David and
Robin Kothari},
title = {Separations in query complexity using cheat sheets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-175}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/175},
eprinttype = {ECCC},
eprint = {TR15-175},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AaronsonBK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Kothari15,
author = {Robin Kothari},
title = {Nearly optimal separations between communication (or query) complexity
and partitions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-195}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/195},
eprinttype = {ECCC},
eprint = {TR15-195},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Kothari15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@phdthesis{DBLP:phd/basesearch/Kothari14,
author = {Robin Kothari},
title = {Efficient algorithms in quantum query complexity},
school = {University of Waterloo, Ontario, Canada},
year = {2014},
url = {https://hdl.handle.net/10012/8625},
timestamp = {Wed, 04 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/phd/basesearch/Kothari14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/Kothari14,
author = {Robin Kothari},
editor = {Ernst W. Mayr and
Natacha Portier},
title = {An optimal quantum algorithm for the oracle identification problem},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science
{(STACS} 2014), {STACS} 2014, March 5-8, 2014, Lyon, France},
series = {LIPIcs},
volume = {25},
pages = {482--493},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2014},
url = {https://doi.org/10.4230/LIPIcs.STACS.2014.482},
doi = {10.4230/LIPICS.STACS.2014.482},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/stacs/Kothari14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BerryCCKS14,
author = {Dominic W. Berry and
Andrew M. Childs and
Richard Cleve and
Robin Kothari and
Rolando D. Somma},
editor = {David B. Shmoys},
title = {Exponential improvement in precision for simulating sparse Hamiltonians},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {283--292},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591854},
doi = {10.1145/2591796.2591854},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BerryCCKS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BelovsCJKM13,
author = {Aleksandrs Belovs and
Andrew M. Childs and
Stacey Jeffery and
Robin Kothari and
Fr{\'{e}}d{\'{e}}ric Magniez},
editor = {Fedor V. Fomin and
Rusins Freivalds and
Marta Z. Kwiatkowska and
David Peleg},
title = {Time-Efficient Quantum Walks for 3-Distinctness},
booktitle = {Automata, Languages, and Programming - 40th International Colloquium,
{ICALP} 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7965},
pages = {105--122},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-39206-1\_10},
doi = {10.1007/978-3-642-39206-1\_10},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/BelovsCJKM13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JefferyKM13,
author = {Stacey Jeffery and
Robin Kothari and
Fr{\'{e}}d{\'{e}}ric Magniez},
editor = {Sanjeev Khanna},
title = {Nested Quantum Walks with Quantum Data Structures},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1474--1485},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.106},
doi = {10.1137/1.9781611973105.106},
timestamp = {Tue, 02 Feb 2021 17:07:29 +0100},
biburl = {https://dblp.org/rec/conf/soda/JefferyKM13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/ChildsKOR13,
author = {Andrew M. Childs and
Robin Kothari and
Maris Ozols and
Martin Roetteler},
editor = {Simone Severini and
Fernando G. S. L. Brand{\~{a}}o},
title = {Easy and Hard Functions for the Boolean Hidden Shift Problem},
booktitle = {8th Conference on the Theory of Quantum Computation, Communication
and Cryptography, {TQC} 2013, May 21-23, 2013, Guelph, Canada},
series = {LIPIcs},
volume = {22},
pages = {50--79},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2013},
url = {https://doi.org/10.4230/LIPIcs.TQC.2013.50},
doi = {10.4230/LIPICS.TQC.2013.50},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/tqc/ChildsKOR13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/CosentinoKP13,
author = {Alessandro Cosentino and
Robin Kothari and
Adam Paetznick},
editor = {Simone Severini and
Fernando G. S. L. Brand{\~{a}}o},
title = {Dequantizing Read-once Quantum Formulas},
booktitle = {8th Conference on the Theory of Quantum Computation, Communication
and Cryptography, {TQC} 2013, May 21-23, 2013, Guelph, Canada},
series = {LIPIcs},
volume = {22},
pages = {80--92},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2013},
url = {https://doi.org/10.4230/LIPIcs.TQC.2013.80},
doi = {10.4230/LIPICS.TQC.2013.80},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tqc/CosentinoKP13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1302-7316,
author = {Andrew M. Childs and
Stacey Jeffery and
Robin Kothari and
Fr{\'{e}}d{\'{e}}ric Magniez},
title = {A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates},
journal = {CoRR},
volume = {abs/1302.7316},
year = {2013},
url = {http://arxiv.org/abs/1302.7316},
eprinttype = {arXiv},
eprint = {1302.7316},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1302-7316.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-4642,
author = {Andrew M. Childs and
Robin Kothari and
Maris Ozols and
Martin Roetteler},
title = {Easy and hard functions for the Boolean hidden shift problem},
journal = {CoRR},
volume = {abs/1304.4642},
year = {2013},
url = {http://arxiv.org/abs/1304.4642},
eprinttype = {arXiv},
eprint = {1304.4642},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-4642.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-5164,
author = {Alessandro Cosentino and
Robin Kothari and
Adam Paetznick},
title = {Dequantizing read-once quantum formulas},
journal = {CoRR},
volume = {abs/1304.5164},
year = {2013},
url = {http://arxiv.org/abs/1304.5164},
eprinttype = {arXiv},
eprint = {1304.5164},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-5164.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Kothari13,
author = {Robin Kothari},
title = {An optimal quantum algorithm for the oracle identification problem},
journal = {CoRR},
volume = {abs/1311.7685},
year = {2013},
url = {http://arxiv.org/abs/1311.7685},
eprinttype = {arXiv},
eprint = {1311.7685},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Kothari13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChildsK12,
author = {Andrew M. Childs and
Robin Kothari},
title = {Quantum Query Complexity of Minor-Closed Graph Properties},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {6},
pages = {1426--1450},
year = {2012},
url = {https://doi.org/10.1137/110833026},
doi = {10.1137/110833026},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChildsK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/ChildsKK12,
author = {Andrew M. Childs and
Shelby Kimmel and
Robin Kothari},
editor = {Leah Epstein and
Paolo Ferragina},
title = {The Quantum Query Complexity of Read-Many Formulas},
booktitle = {Algorithms - {ESA} 2012 - 20th Annual European Symposium, Ljubljana,
Slovenia, September 10-12, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7501},
pages = {337--348},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-33090-2\_30},
doi = {10.1007/978-3-642-33090-2\_30},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/esa/ChildsKK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/JefferyKM12,
author = {Stacey Jeffery and
Robin Kothari and
Fr{\'{e}}d{\'{e}}ric Magniez},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {Improving Quantum Query Complexity of Boolean Matrix Multiplication
Using Graph Collision},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {522--532},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31594-7\_44},
doi = {10.1007/978-3-642-31594-7\_44},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/JefferyKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/ChildsK11,
author = {Andrew M. Childs and
Robin Kothari},
editor = {Thomas Schwentick and
Christoph D{\"{u}}rr},
title = {Quantum query complexity of minor-closed graph properties},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science,
{STACS} 2011, March 10-12, 2011, Dortmund, Germany},
series = {LIPIcs},
volume = {9},
pages = {661--672},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2011},
url = {https://doi.org/10.4230/LIPIcs.STACS.2011.661},
doi = {10.4230/LIPICS.STACS.2011.661},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/stacs/ChildsK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1112-0548,
author = {Andrew M. Childs and
Shelby Kimmel and
Robin Kothari},
title = {The quantum query complexity of read-many formulas},
journal = {CoRR},
volume = {abs/1112.0548},
year = {2011},
url = {http://arxiv.org/abs/1112.0548},
eprinttype = {arXiv},
eprint = {1112.0548},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1112-0548.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/qic/ChildsK10,
author = {Andrew M. Childs and
Robin Kothari},
title = {Limitations on the simulation of non-sparse Hamiltonians},
journal = {Quantum Inf. Comput.},
volume = {10},
number = {7{\&}8},
pages = {669--684},
year = {2010},
url = {https://doi.org/10.26421/QIC10.7-8-7},
doi = {10.26421/QIC10.7-8-7},
timestamp = {Thu, 29 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/qic/ChildsK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/ChildsK10,
author = {Andrew M. Childs and
Robin Kothari},
editor = {Wim van Dam and
Vivien M. Kendon and
Simone Severini},
title = {Simulating Sparse Hamiltonians with Star Decompositions},
booktitle = {Theory of Quantum Computation, Communication, and Cryptography - 5th
Conference, {TQC} 2010, Leeds, UK, April 13-15, 2010, Revised Selected
Papers},
series = {Lecture Notes in Computer Science},
volume = {6519},
pages = {94--103},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-18073-6\_8},
doi = {10.1007/978-3-642-18073-6\_8},
timestamp = {Tue, 14 May 2019 10:00:55 +0200},
biburl = {https://dblp.org/rec/conf/tqc/ChildsK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1011-1443,
author = {Andrew M. Childs and
Robin Kothari},
title = {Quantum query complexity of minor-closed graph properties},
journal = {CoRR},
volume = {abs/1011.1443},
year = {2010},
url = {http://arxiv.org/abs/1011.1443},
eprinttype = {arXiv},
eprint = {1011.1443},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1011-1443.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-21 17:21 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
