J. Thaler

activity

20102022

most citedReliably Learning the ReLU in Polynomial Time

53 citations · 247 across the 33 of their papers we have counts for

collaborators

Showing 2019 · cs.CCShow all

3 papers · 2 filters

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

Approximate degree, secret sharing, and concentration phenomena

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1

The $ε$ -approximate degree $d e g_{ε} (f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $ε$ . The approximate degree…

cs.CC2019

Sign-Rank Can Increase Under Intersection

Mark Bun, Nikhil S. Mande, Justin Thaler

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$ . It is characterized by a matrix-analytic complexi…