Amplification of Bounded Depth Monotone Read-Once Boolean Formulae.

Qian-Ping Gu Akira Maruoka

Published in: SIAM J. Comput. (1991)

Keyphrases

boolean formulae
disjunctive normal form
upper bound
monotone dnf formulas
boolean variables
boolean functions
term dnf
decision trees
lower bound
orders of magnitude
expressive power
phase transition
conjunctive normal form