Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MARKOV INEQUALITIES:
Reports tagged with Markov inequalities:
TR13-032 | 26th February 2013
Mark Bun, Justin Thaler

#### Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

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 ... more >>>

ISSN 1433-8092 | Imprint