53 citations · 247 across the 33 of their papers we have counts for
10 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…
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…
A Nearly Optimal Lower Bound on the Approximate Degree of AC
Mark Bun, Justin Thaler
The approximate degree of a Boolean function is the least degree of a real polynomial that approximates pointwise to error at most…
On the Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden +2
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZ…
Dual Polynomials for Collision and Element Distinctness
Mark Bun, Justin Thaler
The approximate degree of a Boolean function is the minimum degree of a real polynomial that approximates to within error in the $\ell_\inf…