Superpolynomial lower bounds for monotone span programs
type: Item
instance of: scholarly article
title: Superpolynomial lower bounds for monotone span programs
zbMATH Open document ID: 0990.68077
author: László Babai
author: Anna Gál
author: A. Wigderson
published in: Combinatorica
publication date: 2000-05-14T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1446737
zbMATH Keywords: Boolean functions
zbMATH Keywords: computational complexity
zbMATH Keywords: span programs
reviewed by: Marius Zimand
MaRDI profile type: Publication
full work available at URL: s004930050058
OpenAlex ID: W2571456248
DOI: 10.1007/S004930050058
Recommended article: Lower bounds for monotone span programs
Recommended article: Q4228516
Recommended article: Security in Communication Networks
Recommended article: A characterization of span program size and improved lower bounds for monotone span programs
Recommended article: Q4542561
Recommended article: A superpolynomial lower bound for (1,+k(n))-branching programs
Recommended article: An efficient construction of dual monotone span programs
Recommended article: Q4926982
Recommended article: Separating the Power of Monotone Span Programs over Different Fields
Recommended article: Superlinear lower bounds for bounded-width branching programs
description: scientific article; zbMATH DE number 1446737