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

DOI10.1007/BF01844845zbMath0860.05019MaRDI QIDQ1924488

Collette R. Coullard, Lisa Hellerstein

Publication date: 24 November 1996

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

algorithmcomputational learning theorymatroidear decompositionmembership queriestesting independenceport oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

A generalization of Kruskal’s theorem on tensor decomposition, On combinatorial properties of binary spaces, Color-avoiding connected spanning subgraphs with minimum number of edges, Ear‐decompositions, minimally connected matroids and rigid graphs, Matroid Intersection under Restricted Oracles, Combinatorial derived matroids, Global rigidity of periodic graphs under fixed-lattice representations, Matroid connectivity and singularities of configuration hypersurfaces, Connected rigidity matroids and unique realizations of graphs, Complexity of packing common bases in matroids, Global rigidity of generic frameworks on the cylinder, Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids, Sufficient conditions for the global rigidity of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing graphic matroids
• The matroids with the max-flow min-cut property
• A note on the production of matroid minors
• An algorithm to learn read-once threshold formulas, and transformations between learning models
• On inequivalent representations of matroids over finite fields
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• On the Uniqueness of Matroid Representations Over GF(4)
• An Almost Linear-Time Algorithm for Graph Realization
• Computational limitations on learning from examples
• Converting Linear Programs to Network Problems
• Complexity of Matroid Property Algorithms
• Learning read-once formulas with queries
• The Forbidden Minors of Binary Clutters
• A Solution of the Shannon Switching Game