Superpolynomial lower bounds for monotone span programs

DOI10.1007/S004930050058MaRDI QIDQ1977413zbMATH OpenOpenAlexFDO

Authors László Babai, Anna Gál, A. Wigderson

Publication date 14 May 2000

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930050058

zbMATH Keywords

computational complexityBoolean functionsspan programs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Extremal set theory (05D05)

Recommendations

• Lower bounds for monotone span programs
• scientific article; zbMATH DE number 1256780
• Security in Communication Networks
• A characterization of span program size and improved lower bounds for monotone span programs
• scientific article; zbMATH DE number 1775428
• A superpolynomial lower bound for \((1,+k(n))\)-branching programs
• An efficient construction of dual monotone span programs
• Construction of a monotone span program with multiplication
• Separating the Power of Monotone Span Programs over Different Fields
• Superlinear lower bounds for bounded-width branching programs

Cited in

(36)

• On the complexity of computing a random Boolean function over the reals
• Strongly exponential lower bounds for monotone computation
• Span-program-based quantum algorithm for evaluating formulas
• Representations of monotone Boolean functions by linear programs
• Threshold Secret Sharing Requires a Linear Size Alphabet
• Binary Covering Arrays and Existentially Closed Graphs
• On the number of zero-patterns of a sequence of polynomials
• On Linear Secret Sharing for Connectivity in Directed Graphs
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Random constructions and density results
• Improved polynomial secret-sharing schemes
• Towards breaking the exponential barrier for general secret sharing
• On reducibility and symmetry of disjoint NP pairs.
• Secret-sharing schemes for very dense graphs
• scientific article; zbMATH DE number 1775428 (Why is no real title available?)
• Quadratic secret sharing and conditional disclosure of secrets
• Lower bounds for monotone span programs
• Secret sharing schemes for dense forbidden graphs
• Improving the linear programming technique in the search for lower bounds in secret sharing
• A note on monotone complexity and the rank of matrices
• Threshold secret sharing requires a linear-size alphabet
• Secret sharing schemes for ports of matroids of rank 3.
• The automorphism group of projective norm graphs
• On abelian and homomorphic secret sharing schemes
• On pseudorandom subsets in finite fields. I: Measure of pseudorandomness and support of Boolean functions
• Optimal linear secret sharing schemes for graph access structures on six participants
• Succinct computational secret sharing
• Acyclicity programming for sigma-protocols
• Adventures in monotone complexity and TFNP
• Secret-Sharing Schemes: A Survey
• Lifting Nullstellensatz to monotone span programs over any field
• Separating the Power of Monotone Span Programs over Different Fields
• Local bounds for the optimal information ratio of secret sharing schemes
• Security in Communication Networks
• Existence results for cyclotomic orthomorphisms
• A characterization of span program size and improved lower bounds for monotone span programs

This page was built for publication: Superpolynomial lower bounds for monotone span programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1977413)