Superpolynomial lower bounds for monotone span programs (Q1977413)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Superpolynomial lower bounds for monotone span programs
scientific article

    Statements

    Superpolynomial lower bounds for monotone span programs (English)
    0 references
    0 references
    0 references
    0 references
    14 May 2000
    0 references
    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.
    0 references
    Boolean functions
    0 references
    computational complexity
    0 references
    span programs
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references