31 citations · 31 across the 2 of their papers we have counts for
4 papers · 1 filter
Exponential quantum speedup for -Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Robin Kothari, Tony Metger, Ryan O'Donnell +2
We study vector subset sum over : given random vectors from , find a nonempty subset that sums to zero; the smaller , the more difficult it i…
No exponential quantum speedup for anymore
Robin Kothari, Ryan O'Donnell, Kewen Wu
In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case -Short Integer Solution () problem, in a parameter r…
Uniformity testing when you have the source code
Clément L. Canonne, Robin Kothari, Ryan O'Donnell
We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the di…
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
Jeongwan Haah, Robin Kothari, Ewin Tang
We study the problem of learning a Hamiltonian to precision , supposing we are given copies of its Gibbs state at a know…