ECCC-Report TR09-040https://eccc.weizmann.ac.il/report/2009/040Comments and Revisions published for TR09-040en-usWed, 06 May 2009 00:44:34 +0300
Paper TR09-040
| On convex complexity measures |
Pavel Hrubes,
Stasys Jukna,
Alexander Kulikov,
Pavel Pudlak
https://eccc.weizmann.ac.il/report/2009/040 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.
Wed, 06 May 2009 00:44:34 +0300https://eccc.weizmann.ac.il/report/2009/040