### On formal complexity measures

**Speaker:** Pavel Pudlak

**Affiliation:** Academy of Sciences, Czech Republic

**Abstract:** One approach for proving a lower bound on the
complexity of a boolean function *f* is based on defining a measure on
the set *U x V*, where *U={x : f(x)=0 }* and
*V={x : f(x)=1}*. The measure should only be defined on subrectangles of
*U x V* and should satisfy a few simple conditions. Theoretically
one can prove exponential lower bounds on the formula size of *f*
using this approach, but up to now at most quadratic lower bounds have
been obtained. In order to prove larger lower bounds, we need to fully
understand why the measures considered so far cannot give better lower
bounds. Several results showing that certain types of measure cannot
produce large lower bounds have been obtained. In this lecture we
shall survey those results and show some new ones.