53 citations · 247 across the 33 of their papers we have counts for
Showing 2013 · cs.CCShow all
3 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
Annotations for Sparse Data Streams
Amit Chakrabarti, Graham Cormode, Navin Goyal +1
Motivated by cloud computing, a number of recent works have studied annotated data streams and variants thereof. In this setting, a computationally weak verifier (cloud user), lack…
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 …