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.