### DIMACS Theoretical Computer Science Seminar

Title: The quantum adversary method and classical formula size lower bounds

Speaker: **Mario Szegedy**, Rutgers University

Date: September 20, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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 \cite{A03},
and the collision problem.

(joint with Sophie Laplante and Troy Lee)