Amplification by Read-Once Formulas

DOI10.1137/S009753979223633XzbMATH Open0868.94059OpenAlexW2016737198MaRDI QIDQ4337429FDOQ4337429

Moshe Dubiner, Uri Zwick

Publication date: 17 August 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979223633x

Recommendations

• Amplification and percolation (probabilistic Boolean functions)
• Amplification of Bounded Depth Monotone Read-Once Boolean Formulae
• Using amplification to compute majority with small majority gates
• Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
• How Do Read-Once Formulae Shrink?

zbMATH Keywords

boundsamplificationcircuit complexityBoolean formulamonotone read-once formulasrelays with arbitrarily high reliability

Mathematics Subject Classification ID

Boolean functions (06E30)

Cited In (7)

• How Do Read-Once Formulae Shrink?
• Characterizing arithmetic read-once formulae
• Testing Read-Once Formula Satisfaction
• Formula Caching in DPLL
• On linear rewriting systems for Boolean logic and some applications to proof theory
• Optimal explicit small-depth formulas for the coin problem
• Associative and commutative tree representations for Boolean functions

This page was built for publication: Amplification by Read-Once Formulas

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