The List-Decoding Size of Fourier-Sparse Boolean Functions.
Ishay HavivOded RegevPublished in: CoRR (2015)
Keyphrases
- boolean functions
- polynomial size
- uniform distribution
- relevant variables
- dnf formulae
- prime implicants
- bounded treewidth
- threshold functions
- image reconstruction
- high dimensional
- disjunctive normal form
- functional properties
- membership queries
- linear functions
- binary decision diagrams
- computational complexity
- pseudo boolean functions
- read once formulas
- linear threshold
- multi valued
- satisfiability problem