Boolean Functions with Biased Inputs: Approximation and Noise Sensitivity.
Mohsen HeidariS. Sandeep PradhanRamji VenkataramananPublished in: CoRR (2019)
Keyphrases
- boolean functions
- noise sensitivity
- uniform distribution
- prime implicants
- linear functions
- membership queries
- threshold functions
- dnf formulae
- functional properties
- relevant variables
- binary decision diagrams
- linear threshold
- multi valued
- agnostic learning
- orientation estimation
- dnf formulas
- high quality
- polynomial size
- pac learning
- read once formulas