An algorithmic approach using multivariate polynomials for the nonlinearity of Boolean functions.

Emanuele Bellini Teo Mora Massimiliano Sala

Published in: CoRR (2016)

Keyphrases

boolean functions
multivariate polynomials
uniform distribution
agnostic learning
term dnf
membership queries
pac learning
dnf formulas
multi valued
binary decision diagrams
computational learning theory
target concept
mistake bound
learning algorithm
polynomial size
low degree
upper bound