TR09-040 Authors: Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

Publication: 6th May 2009 00:44

Downloads: 2229

Keywords:

Khrapchenko's classical lower bound $n^2$ on the formula size of the

parity function~$f$ can be interpreted as designing a suitable

measure of subrectangles of the combinatorial rectangle

$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we

arrived at the concept of \emph{convex measures}. We prove the

negative result that convex measures are bounded by $O(n^2)$ and

show that several measures considered for proving lower bounds on

the formula size are convex. We also prove quadratic upper bounds on

a class of measures that are not necessarily convex.