Amplification by Read-Once Formulas

DOI10.1137/S009753979223633XMaRDI QIDQ4337429zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

boundsamplificationcircuit complexityBoolean formulamonotone read-once formulasrelays with arbitrarily high reliability

Mathematics Subject Classification ID

Boolean functions (06E30)

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?

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)