file.pdf (260.53 kB)
Download fileApproximation by DNF: Examples and Counterexamples
journal contribution
posted on 2010-07-01, 00:00 authored by Ryan O'Donnell, Karl WimmerSay that f:{0,1}n →{0,1} ε-approximates g : {0,1} n →{0,1} if the functions disagree on at most an ε fraction of points. This paper contains two results about approximation by DNF and other small-depth circuits