From the 1 of 4 linked papers with an AI index.
4 papers
Recognition of algebraic matroids is undecidable
Tobias Boege, Geva Yashfe
The paper shows that there is no algorithm to decide whether a given rank function defines an algebraic matroid, proving the recognition problem undecidable by reducing from Diopha…
On the recognition problem for limits of entropy functions
Geva Yashfe
We prove that there is no algorithm to decide whether a given integer vector is in the closure of the entropic cone . Equivalently, there is no decision proc…
On graphs, homology bases, and triangulated homology spheres
Karim Adiprasito, Marc Lackenby, Juan Souto +1
We describe a construction that takes as input a graph and a basis for its first homology, and returns a triangulation of a 3-dimensional homology sphere. This makes precise an ide…
On entropic and almost multilinear representability of matroids
Lukas Kühne, Geva Yashfe
This article studies two notions of generalized matroid representations motivated by algorithmic information theory and cryptographic secret sharing. The first (entropic representa…