Alexander A. Sherstov

activity

20092024

most citedAn Optimal Separation of Randomized and Quantum Query Complexity

5 citations · 12 across the 9 of their papers we have counts for

collaborators

Showing 2019Show all

3 papers · 1 filter

cs.CC2019★ 4 cited

Vanishing-Error Approximate Degree and QMA Complexity

Alexander A. Sherstov, Justin Thaler

The $ε$ -approximate degree of a function $f : X \to {0, 1}$ is the least degree of a multivariate real polynomial $p$ such that $∣ p (x) - f (x) ∣ \leq ε$ for all $x \in X$ . We det…

cs.CC2019

The Hardest Halfspace

Alexander A. Sherstov

We study the approximation of halfspaces $h : {0, 1}^{n} \to {0, 1}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit cons…

cs.CC2019

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f : {0, 1}^{n} \to {0, 1}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}…