779 citations · 2.6k across the 35 of their papers we have counts for
1 paper · 1 filter
Mark Bun, Robin Kothari, Justin Thaler
The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lowe…