@article {49931,
	title = {Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities},
	journal = {Automata, Languages, and Programming},
	volume = {7965},
	year = {2013},
	note = {ICALP 2013, winner of Best Paper award for Track A},
	pages = {303-314},
	publisher = {Springer Berlin Heidelberg},
	abstract = {The ε-approximate degree of a Boolean function f: { - 1, 1} n  {\textrightarrow} { - 1, 1} is the minimum degree of a real polynomial that approximates f to within ε in the l $\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 ε-approximate degree of the two-level AND-OR tree for any constant ε \&gt; 0. We show that this quantity is Θ(n--√) , closing a line of incrementally larger lower bounds [3,11,21,30,32]. The same lower bound was recently obtained independently by Sherstov using related techniques [25]. 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 [34]. 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.},
	isbn = {978-3-642-39205-4},
	url = {http://dx.doi.org/10.1007/978-3-642-39206-1_26},
	author = {Mark Bun and Justin Thaler},
	editor = {Fomin, FedorV. and Freivalds, Rusin{\v s} and Kwiatkowska, Marta and Peleg, David}
}
