65 citations · 230 across the 37 of their papers we have counts for
Showing 2013 · cs.CCShow all
2 papers · 2 filters
cs.CC2013★ 3 cited
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Mark Bun, Justin Thaler
We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit can…
cs.CC2013
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
Mark Bun, Justin Thaler
The -approximate degree of a Boolean function is the minimum degree of a real polynomial that approximates to within in the …