A note on monotone complexity and the rank of matrices

DOI10.1016/S0020-0190(03)00334-XzbMath1175.68189MaRDI QIDQ1014450

Anna Gál, Pavel Pudlák

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitylower boundsspan programs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Quadratic secret sharing and conditional disclosure of secrets ⋮ Secret-sharing schemes for very dense graphs ⋮ On Linear Secret Sharing for Connectivity in Directed Graphs ⋮ Secret-Sharing Schemes: A Survey ⋮ On abelian and homomorphic secret sharing schemes ⋮ Secret Sharing Schemes for Dense Forbidden Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for monotone span programs
• Combinatorial characterization of read-once formulae
• Superpolynomial lower bounds for monotone span programs
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Simple Constructions of Almost k-wise Independent Random Variables
• Communication Complexity

This page was built for publication: A note on monotone complexity and the rank of matrices