A characterization of span program size and improved lower bounds for monotone span programs

DOI10.1007/s000370100001zbMath1039.68051OpenAlexW1550421702MaRDI QIDQ1405737

Anna Gál

Publication date: 26 August 2003

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

lower boundssecret sharingBoolean formula sizeSpan programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Quadratic secret sharing and conditional disclosure of secrets, Threshold Secret Sharing Requires a Linear Size Alphabet, Communication Lower Bounds via Critical Block Sensitivity, Binary Covering Arrays and Existentially Closed Graphs, On the Readability of Monotone Boolean Formulae, Local bounds for the optimal information ratio of secret sharing schemes, Extension Complexity of Independent Set Polytopes, On the readability of monotone Boolean formulae, On Linear Secret Sharing for Connectivity in Directed Graphs, Secret-Sharing Schemes: A Survey, Adventures in monotone complexity and TFNP, Unnamed Item, Unnamed Item