An o(n) Monotonicity Tester for Boolean Functions over the Hypercube.

Deeparnab Chakrabarty C. Seshadhri

Published in: SIAM J. Comput. (2016)

Keyphrases

boolean functions
uniform distribution
threshold functions
prime implicants
relevant variables
dnf formulae
functional properties
multi valued
binary decision diagrams
bi decomposition
linear functions
truth table
read once formulas
rough sets
statistical queries
membership queries
decision rules