Approximate Polytope Membership Queries.
Sunil AryaGuilherme Dias da FonsecaDavid M. MountPublished in: SIAM J. Comput. (2018)
Keyphrases
- membership queries
- exact learning
- uniform distribution
- boolean functions
- dnf formulas
- efficient learning
- learning algorithm
- query complexity
- pac learning
- equivalence queries
- read once formulas
- target concept
- monotone dnf
- concept classes
- concept class
- convex hull
- agnostic learning
- dnf formulae
- remains np hard
- membership and equivalence queries
- monotone dnf formulas
- boolean formula
- theoretical analysis
- lower bound