Approximating the Distance to Monotonicity of Boolean Functions.

Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova Erik Waingarten

Published in: CoRR (2019)

Keyphrases

boolean functions
uniform distribution
threshold functions
functional properties
dnf formulae
polynomial size
relevant variables
prime implicants
read once formulas
pseudo boolean functions
binary decision diagrams
multi valued
membership queries
machine learning
statistical queries
truth table