*Here is a first guest post from ICALP 2014 kindly written by Clément Canonne. Enjoy it! (This post is also available in PDF. Any typo or typesetting issue with the HTML version is my responsibility.)*

### On DNF approximators for monotone Boolean functions (Eric Blais)

In this talk, Eric Blais presented joint work with Johan Håstad, Rocco Servedio and Li-Yang Tan, concerned with Boolean functions. More precisely, "the simplest representations of functions": DNF (Disjunctive Normal Form) formulas.For a little bit of background, recall that a Boolean function f : {0,1}

^{n}→{0,1} defined on the hypercube [2] is a DNF if it can be written as

A nice property of DNF formulas is that they are arguably amongst the simplest of all representations of Boolean functions; while formulas of depth ≥ 3 are a nightmare, DNFs have been extensively studied, and by now "Everything is known about them". Well,

*almost*everything.

Indeed, amidst other facts, we have that

**Theorem 3**(Korshunov '81, Kuznetsov '83). A random Boolean function can be computed by DNFs of size Θ(2

^{n}∕log n) (and requires that much).

*exact*computation of Boolean functions by DNFs, what about

*approximate*representation of a function? That is, what about the size required to approximate a Boolean function by a DNF, if one allows error ε (as a fraction of the inputs).

This leads to the notion of

**DNF approximator complexity**; and here again some results – much more recent results:

**Theorem 4**(Blais–Tan ’13). Every Boolean function can be approximated by a DNF of size O(2

^{n}∕log n). Furthermore, our all friend PARITY

_{n}only needs DNF size O(2

^{(1-2ε)n}).

*way*better than 2

^{n-1}. So, again – are we done here? And, again... not quite. This brings us to the main point of the paper, namely: what about

*monotone*functions? Can they be computed more efficiently? Approximated more efficiently? (Recall that a Boolean function f is monotone if x ≼ y implies f(x) ≤ f(y), where ≼ is the coordinate-wise partial order on bit-strings.)

As a starter: no.

**Theorem 5**(Folklore) Every monotone Boolean function can be computed by a DNF of size O(2

^{n}∕n

^{1/2}) (using subcubes rooted on each min-term); and again, this is tight for PARITY.

**Theorem 6**(Quine ’54). To compute monotone Boolean functions, monotone DNFs are the best amongst DNFs.

**Theorem 7**(Blais–Hastad–Servedio–Tan ’14). Every monotone Boolean function can be approximated by a DNF of size O(2

^{n}∕2

^{Ω(n1/2)}).

- Regularity lemma: the world would be much simpler if all subcubes
were rooted on the same level of the hypercube; so first, reduce it to
this case (writing f = f
_{1}+ .....+ f_{k}, each f_{i}has this property) - then, approximate independently each f
_{i}, using a probabilistic argument (via random sampling), to prove there exists a good approximator for all f_{i}’s, and then stitching them together.

_{n}. The proof goes by a counting argument and concentration of measure on the hypercube (every or almost every input is on the middle "belt" of the hypercube; but each subcube thus has to be rooted there, and each cannot cover too much... so many are needed)

So, approximation

*does*buy us a lot. But clearly, using negations shouldn’t, should it? Why would allowing non-monotone DNF’s to approximate monotone functions

*ever*help? (

**Hint:**it does.) (Yep.)

**Theorem 8**(Blais–Hastad–Servedio–Tan ’14). For every n, there exists ε

_{n}and f : {0,1}

^{6n}→{0,1} such that

- f can be ε
_{n}-approximated by DNFs of size O(n); - any
*monotone*DNF ε_{n}-approximating f must have size Ω(n^{2}).

**The upshot:**

*exact*computation and

*approximate*computation have intrinsically

**very**different properties!

Eric then concluded with an open question: namely, how to improve/better understand the gap between approximating functions with monotone DNF vs. approximating them with general DNF’s (the currently known gap in the size being quite huge – almost exponential). Additionally, how to get a separation as in the mind-boggling theorem above, but changing the quantifiers – that is, for a constant ε independent of n?

Also, can someone fix my intuition? I think it’s broken.

## No comments:

Post a Comment