Generating all maximal independent sets of bounded-degree hypergraphs

Nina Mishra, Leonard Pitt

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
Pages211-217
Number of pages7
DOIs
StatePublished - Jan 1 1997
EventProceedings of the 1997 10th Annual Conference on Computational Learning Theory - Nashville, TN, USA
Duration: Jul 6 1997Jul 9 1997

Other

OtherProceedings of the 1997 10th Annual Conference on Computational Learning Theory
CityNashville, TN, USA
Period7/6/977/9/97

ASJC Scopus subject areas

  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Generating all maximal independent sets of bounded-degree hypergraphs'. Together they form a unique fingerprint.

Cite this