Abstract:

We introduce two new complexity measures for Boolean functions,
which we name $\spi$ and $\mpi$.  The quantity $\spi$ has been
emerging through a line of research on quantum query complexity
lower bounds via the so-called quantum adversary method
culminating in the realization of Spalek and Szegedy that many
of the known different formulations are in fact equivalent.
Given that $\spi$ turns out to be such a robust invariant of a
function, we begin to investigate this quantity in its own right
and see that it also has applications to classical complexity
theory.

As a surprising application we show that $\spi^2(f)$ is a lower
bound on the formula size, and even, up to a constant
multiplicative factor, the probabilistic formula size of $f$.
We show that several formula size lower bounds in the
literature, specifically Khrapchenko and its extensions,
including a key lemma of Hastad, are in fact special cases of
our method. The second quantity we introduce, $\mpi(f)$, is
always at least as large as $\spi(f)$, and is derived from
$\spi$ in such a way that $\mpi^2(f)$ remains a lower bound on
formula size.

Our main result is proven via a combinatorial lemma which
relates the square of the spectral norm of a matrix to the
squares of the spectral norms of its submatrices.  The
generality of this lemma implies that our methods can also be
used to lower bound the communication complexity of relations,
and a related combinatorial quantity, the rectangle partition
number.

To exhibit the strengths and weaknesses of our methods, we look
at the $\spi$ and $\mpi$ complexity of a few examples, including
the recursive majority of three function, a function defined by
Ambainis, and the collision problem.

Joint work with Sophie Laplante and Troy Lee.