scientific article; zbMATH DE number 1256780

MaRDI QIDQ4228516zbMATH OpenFDO

Authors László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, A. Wigderson

Publication date 5 July 1999

zbMATH Keywords

bipartite graphsdensityextremal graph theorylower boundmonotone circuitsmonotone formulaemonotone span programssuperpolynomial lower bounds

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Superpolynomial lower bounds for monotone span programs
• scientific article; zbMATH DE number 1775428
• A characterization of span program size and improved lower bounds for monotone span programs
• Lower bounds for monotone span programs

Cited in

(14)

• On the spectrum of projective norm-graphs
• A note on monotone complexity and the rank of matrices
• On arithmetic branching programs
• Superpolynomial lower bounds for monotone span programs
• On abelian and homomorphic secret sharing schemes
• scientific article; zbMATH DE number 1775428 (Why is no real title available?)
• More on a problem of Zarankiewicz
• Binary Covering Arrays and Existentially Closed Graphs
• A Result on the Distribution of Quadratic Residues with Applications to Elliptic Curve Cryptography
• Construction of self dual codes from graphs
• Lower bounds for monotone span programs
• Applications of random algebraic constructions to hardness of approximation
• LCD codes over finite fields
• Subgraphs of the projective norm graph

This page was built for publication:

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