Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Mark Bun, Justin Thaler

Abstract

The $\epsilon$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $\epsilon$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the $\epsilon$-approximate degree of the two-level AND-OR tree for any constant $\epsilon > 0$. We show that this quantity is $\Theta(\sqrt{n})$, closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of \v{S}palek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.
BibTeX
@article{bun2015dual,
  author = {Mark Bun and Justin Thaler},
  title = {{Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities}},
  journal = {Inf. Comput.},
  year = {2015},
  doi = {10.1016/j.ic.2014.12.003},
}
Figure