53 citations · 247 across the 33 of their papers we have counts for
4 papers · 1 filter
Vanishing-Error Approximate Degree and QMA Complexity
Alexander A. Sherstov, Justin Thaler
The -approximate degree of a function is the least degree of a multivariate real polynomial such that for all . We det…
Approximate degree, secret sharing, and concentration phenomena
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1
The -approximate degree of a Boolean function is the least degree of a real-valued polynomial that approximates pointwise to error . The approximate degree…
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
Scott Aaronson, Robin Kothari, William Kretschmer +1
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Lauren…
Sign-Rank Can Increase Under Intersection
Mark Bun, Nikhil S. Mande, Justin Thaler
The communication class is a communication analog of the Turing Machine complexity class . It is characterized by a matrix-analytic complexi…