The quantum adversary method and classical formula size lower bounds

Sophie Laplante, Troy Lee, Mario Szegedy

We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has b…