On entropic and almost multilinear representability of matroids

Kühne L, Yashfe G (Submitted)
ArXiv: 2206.03465.

Preprint | Eingereicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Kühne, LukasUniBi ; Yashfe, Geva
Abstract / Bemerkung
This article is concerned with two notions of generalized matroid representations motivated by information theory and computer science. The first involves representations by discrete random variables and the second approximate representations by subspace arrangements. In both cases we show that there is no algorithm that checks whether such a representation exists. As a consequence, the conditional independence implication problem is undecidable, which gives an independent answer to a question in information theory by Geiger and Pearl that was recently also answered by Cheuk Ting Li. These problems are closely related to problems of characterizing the achievable rates in certain network coding problems and of constructing secret sharing schemes. Our methods to approach these problems are mostly algebraic. Specifically, they involve reductions from the uniform word problem for finite groups and the word problem for sofic groups.
Erscheinungsjahr
2022
Zeitschriftentitel
ArXiv: 2206.03465
Page URI
https://pub.uni-bielefeld.de/record/2982640

Zitieren

Kühne L, Yashfe G. On entropic and almost multilinear representability of matroids. ArXiv: 2206.03465. Submitted.
Kühne, L., & Yashfe, G. (Submitted). On entropic and almost multilinear representability of matroids. ArXiv: 2206.03465. https://doi.org/10.48550/ARXIV.2206.03465
Kühne, Lukas, and Yashfe, Geva. Submitted. “On entropic and almost multilinear representability of matroids”. ArXiv: 2206.03465.
Kühne, L., and Yashfe, G. (Submitted). On entropic and almost multilinear representability of matroids. ArXiv: 2206.03465.
Kühne, L., & Yashfe, G., Submitted. On entropic and almost multilinear representability of matroids. ArXiv: 2206.03465.
L. Kühne and G. Yashfe, “On entropic and almost multilinear representability of matroids”, ArXiv: 2206.03465, Submitted.
Kühne, L., Yashfe, G.: On entropic and almost multilinear representability of matroids. ArXiv: 2206.03465. (Submitted).
Kühne, Lukas, and Yashfe, Geva. “On entropic and almost multilinear representability of matroids”. ArXiv: 2206.03465 (Submitted).
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Quellen

arXiv: 2206.03465

Suchen in

Google Scholar