  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.
