The ε-approximate degree of a Boolean function f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates f to within ε in the ℓ∞ 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 ε-approximate degree of the two-level AND-OR tree for any constant ε>0. We show that this quantity is Θ(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 Š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.
We investigate the best constant J(n,d) such that Jackson's inequality infdeg(g)≤d∥f−g∥∞≤J(n,d)s(f), holds for all functions f on the hypercube {0,1}n, where s(f) denotes the sensitivity of f. We show that the quantity J(n,0.499n) is bounded below by an absolute positive constant, independent of n. This complements Wagner's theorem, which establishes that $J(n,d)\leq 1 $. As a first application we show that reverse Bernstein inequality fails in the tail space L≥0.499n1 improving over previously known counterexamples in L≥Cloglog(n)1. As a second application, we show that there exists a function f:{0,1}n→[−1,1] whose sensitivity s(f) remains constant, independent of n, while the approximate degree grows linearly with n. This result implies that the sensitivity theorem s(f)≥Ω(deg(f)C) fails in the strongest sense for bounded real-valued functions even when deg(f) is relaxed to the approximate degree. We also show that in the regime d=(1−δ)n, the bound J(n,d)≤Cmin{δ,max{δ2,n−2/3}} holds. Moreover, when restricted to symmetric real-valued functions, we obtain Jsymmetric(n,d)≤C/d and the decay 1/d is sharp. Finally, we present results for a subspace approximation problem: we show that there exists a subspace E of dimension 2n−1 such that infg∈E∥f−g∥∞≤s(f)/n holds for all f.