On P versus NP∧co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size less than or equal to N then f also has a (deterministic) decision tree of size exp(O(log n log(2) N)). We show that this simulation can not be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp(Ohm(log(2) N)) where N is the total number of monomials in minimal DNFs for f and -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. Other examples have the additional property that f is in AC(0).