TR97-023 Authors: S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

Publication: 3rd June 1997 19:01

Downloads: 1562

Keywords:

It is known that if a Boolean function f in n variables

has a DNF and a CNF of size at most N then f also has a

(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.

We show that this simulation {\em cannot} be made polynomial: we

exhibit explicit Boolean functions f that require deterministic

trees of size $\exp(\Omega(\log^2 N))$ where N is the total

number of monomials in minimal DNFs for f and \neg f. Moreover,

we exhibit new examples of explicit Boolean functions that require

deterministic read-once branching programs of exponential size

whereas both the functions and their negations have small

nondeterministic read-once branching programs. One example results

from the Bruen-Blokhuis bound on the size of nontrivial blocking

sets in projective planes: it is remarkably simple and combinatorially

clear. Whereas other examples have the additional property that f

is in AC^0.