Independence and port oracles for matroids, with an application to computational learning theory

Collette R. Coullard, Lisa Hellerstein

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Given a matroid M with distinguished element e, a port oracle with respect to e reports whether or not a given subset contains a circuit that contains e. The first main result of this paper is an algorithm for computing an e-based ear decomposition (that is, an ear decomposition every circuit of which contains element e) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case that M is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation for M. Thus, this algorithm solves a problem in computational learning theory; it learns the class of binary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroid M. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.

    Original languageEnglish (US)
    Pages (from-to)189-208
    Number of pages20
    JournalCombinatorica
    Volume16
    Issue number2
    DOIs
    StatePublished - 1996

    ASJC Scopus subject areas

    • Discrete Mathematics and Combinatorics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Independence and port oracles for matroids, with an application to computational learning theory'. Together they form a unique fingerprint.

    Cite this