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

DOI10.1007/BF01844845MaRDI QIDQ1924488zbMATH OpenFDO

Authors Collette R. Coullard, Lisa Hellerstein

Publication date 24 November 1996

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01844845

zbMATH Keywords

algorithmcomputational learning theoryear decompositionmatroidmembership queriesport oracletesting independence

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1003264
• scientific article; zbMATH DE number 56949
• scientific article; zbMATH DE number 3918383
• Learning families of closed sets in matroids
• scientific article; zbMATH DE number 3858856

Cites work

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

Cited in

(19)

• Connected rigidity matroids and unique realizations of graphs
• Complexity of packing common bases in matroids
• Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
• Global rigidity of periodic graphs under fixed-lattice representations
• Matroid connectivity and singularities of configuration hypersurfaces
• Global rigidity of generic frameworks on the cylinder
• Sufficient conditions for the global rigidity of graphs
• Combinatorial derived matroids
• Learning families of closed sets in matroids
• scientific article; zbMATH DE number 1003264 (Why is no real title available?)
• scientific article; zbMATH DE number 3918383 (Why is no real title available?)
• Query complexity of matroids
• On combinatorial properties of binary spaces
• A generalization of Kruskal’s theorem on tensor decomposition
• Color-avoiding connected spanning subgraphs with minimum number of edges
• Ear‐decompositions, minimally connected matroids and rigid graphs
• Matroid Intersection under Restricted Oracles
• On the enumeration of non-dominated matroids with imprecise weights
• Matroid polytopes with small rank

This page was built for publication: Independence and port oracles for matroids, with an application to computational learning theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924488)