Abstract
We show that any monotone function with a read-k CNF representation can be learned in terms of its DNF representation with membership queries alone in time polynomial in the DNF size and n (the; number of variables) assuming k is some fixed constant. The problem is motivated by the well-studied open problem of enumerating all maximal independent sets of a given hypergraph. Our algorithm gives a solution for the bounded degree case and works even if the hypergraph is not input, but rather only queries are available as to which sets are independent.
| Original language | English (US) |
|---|---|
| Pages | 211-217 |
| Number of pages | 7 |
| DOIs | |
| State | Published - 1997 |
| Event | Proceedings of the 1997 10th Annual Conference on Computational Learning Theory - Nashville, TN, USA Duration: Jul 6 1997 → Jul 9 1997 |
Other
| Other | Proceedings of the 1997 10th Annual Conference on Computational Learning Theory |
|---|---|
| City | Nashville, TN, USA |
| Period | 7/6/97 → 7/9/97 |
ASJC Scopus subject areas
- Computational Mathematics