### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms |

Publisher | Publ by ACM |

Pages | 328-335 |

Number of pages | 8 |

ISBN (Print) | 0898713293 |

State | Published - Jan 1 1994 |

Event | Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA Duration: Jan 23 1994 → Jan 25 1994 |

### Publication series

Name | Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms |
---|---|

City | Arlington, VA, USA |

Period | 1/23/94 → 1/25/94 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Learning binary matroid ports'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms*(pp. 328-335). (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms). Publ by ACM.