PDF《Approximation by DNF: Examples and》

Approximation by DNF: Examples and Counterexamples Ryan O'

Donnell Carnegie Mellon University odonnell@cs.

cmu.edu Karl Wimmer Carnegie Mellon University [email protected] May 1,

2007 Abstract Say 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: (1) For every constant

0 <

<

1/2 there is a DNF of size 2O( √ n) that -approximates the Majority function on n bits, and this is optimal up to the constant in the exponent. (2) There is a monotone function F : {0, 1}n → {0, 1} with total in?uence (AKA average sensitivity) I(F) ≤ O(log n) such that any DNF or CNF that .01-approximates F requires size 2?(n/ log n) and such that any unbounded fan-in AND-OR-NOT circuit that .01-approximates F requires size ?(n/ log n). This disproves a conjecture of Benjamini, Kalai, and Schramm (appearing in [BKS99, Kal00, KS05]).

1 Introduction 1.1 De?nitions This paper is concerned with approximating boolean functions f : {0, 1}n → {0, 1} by DNF formulas of small size. Let us ?rst give the requisite de?nitions. Circuits: We will consider single-output circuits composed of unbounded fan-in AND and OR gates over the input literals (inputs and negated inputs). The size of a circuit is the number of AND and OR gates it contains, and the depth of the circuit is the number of AND and OR gates on the longest path from an input bit to the output gate. We will also make the not completely standard de?nition that the width of a circuit is the maximum, over all AND and OR gates, of the number of literals feeding into the gate. We will only be concerned with constant-depth circuits in this paper, and we will be particularly interested in depth 2. We assume circuits of depth

2 are always given by an OR of ANDs of literals, in which case they are DNFs, or by an AND of ORs of literals, in which case they are CNFs. The ORs in a DNF are called its terms and the ANDs in a CNF are called its clauses. Finally, we will often identify a circuit over n input bits with the boolean function {0, 1}n → {0, 1} that it computes. Approximation: Given two functions f, g : {0, 1}n → {0, 1}, we will say that f -approximates g, or f is an -approximator for g, if the fraction of inputs in {0, 1}n on which they disagree is at most . We will also write this as Pr x [f(x) = g(x)] ≤ , with the convention that boldface letters are random variables, and that they are drawn from the uniform distribution on {0, 1}n unless otherwise speci?ed. We will later need the following well known observation, showing that small-size circuits are well approximated by small-width circuits: Observation 1.1 If C is a circuit of size s, then for every >

0 there is a simpli?cation C of C that -approximates C and has width at most log(s/ ).1 By simpli?cation we mean that C is obtained from C by replacing some of its gates with constants, so that C has size and depth no more than C, and C is a DNF (respectively, CNF) if C is. Proof: Consider any gate in C that is connected to at least log(s/ ) input literals. If such a gate is an AND gate, replace it with a 0;

and if it is an OR gate, replace it with a 1. This gives us C , which clearly has width at most log(s/ ). Now on a uniformly random input, the probability that a particular replacement a?ects C'

s computation is at most 2? log(s/ ) = /s. Since C has at most s gates, the probability that any replacement a?ects its computation is at most , by the union bound. Thus C is an -approximator for C.