Representing matroids over the reals is R-complete

DOI10.46298/DMTCS.10810MaRDI QIDQ6606993zbMATH OpenFDO

Authors Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow

Publication date 17 September 2024

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/DMTCS.10810

zbMATH Keywords

combinatoricscomputational complexitycomputer sciencemathematics

Mathematics Subject Classification ID

Combinatorics (05-XX)

Recommendations

• On Matroid Representability and Minor Problems
• On the complex-representable excluded minors for real-representability
• Representability of matroids by c-arrangements is undecidable
• On Matroids Representable over 𝐺𝐹(3) and Other Fields
• Testing orientability for matroids is NP-complete

Cites work

• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• A parameterized view on matroid optimization problems
• Bounding the radii of balls meeting every connected component of semi-algebraic sets
• Certifying non-representability of matroids over prime fields
• Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Complexity of Matroid Property Algorithms
• Complexity of some geometric and topological problems
• Excluded minors for matroids satisfying Kinser's inequalities
• Excluded minors for the class of split matroids
• Finding branch-decompositions of matroids, hypergraphs, and more
• Fixed points, Nash equilibria, and the existential theory of the reals
• Flag matroids: algebra and geometry
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 3518931 (Why is no real title available?)
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• Integer realizations of disk and segment graphs
• Intersection graphs of rays and grounded segments
• Intersection graphs of segments
• Matroid Complexity and Nonsuccinct Descriptions
• Matroid matching and some applications
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On Matroid Representability and Minor Problems
• On restricted nonnegative matrix factorization
• On the computational complexity of decision problems about multi-player Nash equilibria
• On the efficiency of representability tests for matroids
• On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
• Oriented Matroids
• Realization spaces of 4-polytopes are universal
• Representative sets and irrelevant vertices: new tools for kernelization
• Solving Rota's conjecture
• Sphere and dot product representations of graphs
• Testing branch-width
• The art gallery problem is \(\exists \mathbb{R}\)-complete
• The asymptotic number of geometries
• The complexity of drawing a graph in a polygonal region
• The complexity of positive semidefinite matrix factorization
• The complexity of tensor rank
• The complexity of the Hausdorff distance
• Topological art in simple galleries

This page was built for publication: Representing matroids over the reals is \(\exists \mathbb{R}\)-complete

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