On the Complexity of Boolean Functions Computed by Lazy Oracles.

Paul E. S. Dunne Paul H. Leng Gerald F. Nwana

Published in: IEEE Trans. Computers (1995)

Keyphrases

boolean functions
uniform distribution
polynomial size
functional properties
statistical queries
membership queries
worst case
prime implicants
bounded treewidth
threshold functions
dnf formulae
relevant variables
bi decomposition
truth table
machine learning
read once formulas
multi valued
computational complexity