Learning binary matroid ports

In this paper we present an algorithm that extends previous research in two distinct fields - matroid theory and computational learning theory. In matroid theory terms, our algorithm proves a constructive version of an early theorem of Lehman. Lehman proved that the port of a connected matroid uniquely determines the matroid. Following previous research on matroid oracle algorithms, we introduce a new oracle, the port oracle, which determines whether a set of elements contains a member of the port. Our algorithm constructs a binary matrix representation of a connected binary matroid in polynomial time via a polynomial number of calls to the port oracle. The algorithm is non-trivial, and does not follow directly from Lehman's proof. (By generalizing the techniques of our algorithm, we can also prove that for arbitrary connected matroids, an independence oracle can be simulated via a polynomial number of calls to a port oracle.) In computational learning theory terms, our algorithm learns the class of binary matroid port functions in polynomial time using membership queries. There are few non-trivial classes known to be learnable in polynomial time in this model. Our algorithm generalizes results of Angluin, Hellerstein, and Karpinski, and Raghavan and Schach, who showed that certain subclasses of the binary matroid port functions are learnable in polynomial time using membership queries. Our algorithm also represents the first use of matroid theory techniques in solving computational learning theory problems.