On converting CNF to DNF

We study how big the blow-up in size can be when one switches between the CNF and DNF representations of Boolean functions. For a function f:{0,1}n→{0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0⩽m⩽2n-1, let dnfsize(m,n) be the maximum dnfsize(f) for a function f:{0,1}n→{0,1} with cnfsize(f)⩽m. We show that there are constants c1,c2⩾1 and ε>0, such that for all large n and all m∈[1εn,2εn], we have2n-c1(n/log(m/n))⩽dnfsize(m,n)⩽2n-c2(n/log(m/n)).In particular, when m is the polynomial nc, we get dnfsize(nc,n)=2n-θ(c-1(n/logn)).