Superpolynomial lower bounds for monotone span programs (Q1977413)

Span programs are a linear algebraic model for computing Boolean functions. A span program consists of a vector \(w \neq 0\) in a linear space and of \(2n\) linear subspaces associated to the set of \(n\) variables \(x_1, \ldots, x_n\) and to their negations. The program defines a Boolean function \(f(x_1, \ldots, x_n)\) by \(f(\alpha_1, \ldots, \alpha_n) = 1\) exactly when \(w\) belongs to the span of the subspaces associated to \(\alpha_1, \ldots, \alpha_n\) in the natural way. A span program is monotone if the subspaces associated to the negated variables are all equal to the null subspace. The size of a span program is the sum of the dimensions of the subspaces associated to literals. The main result shows that there is a family of monotone Boolean functions \(\{f_n\}\), \(f_n\) having \(n\) variables and computable in NP, that requires monotone span programs of size at least \(n^{\Omega(\log n / \log \log n)}.\) The proof is based on an analysis of Paley-type bipartite graphs via Weil character sum estimates.