On Computing Boolean Functions by Sparse Real Polynomials.

Matthias Krause Pavel Pudlák

Published in: FOCS (1995)

Keyphrases

boolean functions
uniform distribution
multi valued
membership queries
functional properties
prime implicants
threshold functions
read once formulas
lagrange interpolation
machine learning
search algorithm
disjunctive normal form
bi decomposition
dnf formulae