Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids.

Hadley Black Deeparnab Chakrabarty C. Seshadhri

Published in: FOCS (2023)

Keyphrases

boolean functions
uniform distribution
threshold functions
dnf formulae
multi valued
relevant variables
linear threshold
rough sets
polynomial size
read once formulas
lower bound
learning theory
binary decision diagrams
dnf formulas
linear functions
pseudo boolean functions