Representing Matroids over the Reals is $\exists \mathbb R$-complete
Fuente:
arXiv
Salvato in:
| Autori principali: | Kim, Eun Jung, de Mesmay, Arnaud, Miltzow, Tillmann |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Documenti analoghi
Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
di: Meijer, Lucas, et al.
Pubblicazione: (2025)
di: Meijer, Lucas, et al.
Pubblicazione: (2025)
Beyond Bits: An Introduction to Computation over the Reals
di: Miltzow, Tillmann
Pubblicazione: (2026)
di: Miltzow, Tillmann
Pubblicazione: (2026)
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
di: Abrahamsen, Mikkel, et al.
Pubblicazione: (2020)
di: Abrahamsen, Mikkel, et al.
Pubblicazione: (2020)
Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
di: Bertschinger, Daniel, et al.
Pubblicazione: (2022)
di: Bertschinger, Daniel, et al.
Pubblicazione: (2022)
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
di: Borzechowski, Michaela, et al.
Pubblicazione: (2023)
di: Borzechowski, Michaela, et al.
Pubblicazione: (2023)
The Existential Theory of the Reals as a Complexity Class: A Compendium
di: Schaefer, Marcus, et al.
Pubblicazione: (2024)
di: Schaefer, Marcus, et al.
Pubblicazione: (2024)
On Classifying Continuous Constraint Satisfaction Problems
di: Miltzow, Tillmann, et al.
Pubblicazione: (2021)
di: Miltzow, Tillmann, et al.
Pubblicazione: (2021)
Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)
Atropos-k is PSPACE-complete
di: Yang, Chao, et al.
Pubblicazione: (2024)
di: Yang, Chao, et al.
Pubblicazione: (2024)
Isotropy and completeness indices of multilinear maps
di: Chen, Qiyuan, et al.
Pubblicazione: (2025)
di: Chen, Qiyuan, et al.
Pubblicazione: (2025)
Maker-Maker games of rank 4 are PSPACE-complete
di: Galliot, Florian, et al.
Pubblicazione: (2025)
di: Galliot, Florian, et al.
Pubblicazione: (2025)
Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
di: Concha-Vega, Pablo
Pubblicazione: (2026)
di: Concha-Vega, Pablo
Pubblicazione: (2026)
Arithmetic Circuits and Neural Networks for Regular Matroids
di: Hertrich, Christoph, et al.
Pubblicazione: (2025)
di: Hertrich, Christoph, et al.
Pubblicazione: (2025)
4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
di: Galliot, Florian
Pubblicazione: (2025)
di: Galliot, Florian
Pubblicazione: (2025)
Permanents of random matrices over finite fields
di: Hunter, Zach, et al.
Pubblicazione: (2026)
di: Hunter, Zach, et al.
Pubblicazione: (2026)
Lions and Contamination: Trees and General Graphs
di: Kim, Dohoon, et al.
Pubblicazione: (2026)
di: Kim, Dohoon, et al.
Pubblicazione: (2026)
NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
di: Yang, Chao, et al.
Pubblicazione: (2024)
di: Yang, Chao, et al.
Pubblicazione: (2024)
Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
di: Förster, Henry, et al.
Pubblicazione: (2023)
di: Förster, Henry, et al.
Pubblicazione: (2023)
Oracle Separations for RPH
di: Hamm, Thekla, et al.
Pubblicazione: (2025)
di: Hamm, Thekla, et al.
Pubblicazione: (2025)
Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
di: Mary, Arnaud
Pubblicazione: (2024)
di: Mary, Arnaud
Pubblicazione: (2024)
Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
di: Casteigts, Arnaud, et al.
Pubblicazione: (2020)
di: Casteigts, Arnaud, et al.
Pubblicazione: (2020)
Some structural complexity results for $\exists\mathbb R$
di: Meer, Klaus, et al.
Pubblicazione: (2025)
di: Meer, Klaus, et al.
Pubblicazione: (2025)
Degenerate crossing number and signed reversal distance
di: Fuladi, Niloufar, et al.
Pubblicazione: (2023)
di: Fuladi, Niloufar, et al.
Pubblicazione: (2023)
Real Stability and Log Concavity are coNP-Hard
di: Chin, Tracy
Pubblicazione: (2024)
di: Chin, Tracy
Pubblicazione: (2024)
Flat origami is Turing Complete
di: Hull, Thomas C., et al.
Pubblicazione: (2023)
di: Hull, Thomas C., et al.
Pubblicazione: (2023)
Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
di: Notarantonio, Hadrien, et al.
Pubblicazione: (2023)
di: Notarantonio, Hadrien, et al.
Pubblicazione: (2023)
Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
di: Dikstein, Yotam, et al.
Pubblicazione: (2023)
di: Dikstein, Yotam, et al.
Pubblicazione: (2023)
Query complexity of Boolean functions on the middle slice of the cube
di: Gerbner, Dániel, et al.
Pubblicazione: (2023)
di: Gerbner, Dániel, et al.
Pubblicazione: (2023)
On Approximability of Satisfiable k-CSPs: IV
di: Bhangale, Amey, et al.
Pubblicazione: (2023)
di: Bhangale, Amey, et al.
Pubblicazione: (2023)
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
di: Li, Xin, et al.
Pubblicazione: (2023)
di: Li, Xin, et al.
Pubblicazione: (2023)
On a Hierarchy of Spectral Invariants for Graphs
di: Arvind, V., et al.
Pubblicazione: (2023)
di: Arvind, V., et al.
Pubblicazione: (2023)
A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
di: Gan, Luyining, et al.
Pubblicazione: (2023)
di: Gan, Luyining, et al.
Pubblicazione: (2023)
Low-Degree Polynomials Are Good Extractors
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)
Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)
Refuting Perfect Matchings in Spectral Expanders is Hard
di: Biswas, Ari, et al.
Pubblicazione: (2025)
di: Biswas, Ari, et al.
Pubblicazione: (2025)
A Note on the Complexity of Directed Clique
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)
Direct Product Primality Testing of Graphs is GI-hard
di: Calderoni, Luca, et al.
Pubblicazione: (2020)
di: Calderoni, Luca, et al.
Pubblicazione: (2020)
Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)
Hunting a rabbit: complexity, approximability and some characterizations
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2025)
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2025)
On the Keevash-Knox-Mycroft Conjecture
di: Gan, Luyining, et al.
Pubblicazione: (2022)
di: Gan, Luyining, et al.
Pubblicazione: (2022)
Documenti analoghi
-
Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
di: Meijer, Lucas, et al.
Pubblicazione: (2025) -
Beyond Bits: An Introduction to Computation over the Reals
di: Miltzow, Tillmann
Pubblicazione: (2026) -
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
di: Abrahamsen, Mikkel, et al.
Pubblicazione: (2020) -
Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
di: Bertschinger, Daniel, et al.
Pubblicazione: (2022) -
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
di: Borzechowski, Michaela, et al.
Pubblicazione: (2023)