Online seminar on Algorithmic Aspects of Information Theory, March 11
3 views
Skip to first unread message
Andrei Romashchenko
Mar 5, 2026, 4:43:30 AM (7 days ago) Mar 5
to Kolmogorov seminar on complexity
Dear colleagues,
The next meeting of the seminar AAIT is scheduled on March 11 (Wednesday), at 17h00 of Paris time (see https://time.is/CET).
Our speaker is Carles Padró (Universitat Politècnica de Catalunya).
Talk title: "Interaction between skew-representability, tensor products, extension properties, and rank inequalities."
Abstract: Skew-representable matroids form a fundamental class in matroid theory, bridging combinatorics and linear algebra. They play an important role in areas such as coding theory, optimization, and combinatorial geometry, where linear structure is crucial for both theoretical insights and algorithmic applications. Since deciding skew-representability is computationally intractable, much effort has been focused on identifying necessary or sufficient conditions for a matroid to be skew-representable.
In this paper, we introduce a novel approach to studying skew-representability and structural properties of matroids and polymatroid functions via tensor products. We provide a characterization of skew-representable matroids, as well as of those representable over skew fields of a given prime characteristic, in terms of tensor products. As an algorithmic consequence, we show that deciding skew-representability, or representability over a skew field of fixed prime characteristic, is co-recursively enumerable: that is, certificates of non-skew-representability — in general or over a fixed prime characteristic — can be verified. We also prove that every rank-3 matroid admits a tensor product with any uniform matroid and give a construction yielding the unique freest tensor product in this setting. Finally, as an application of the tensor product framework, we give a new proof of Ingleton's inequality and, more importantly, derive the first known linear rank inequality for folded skew-representable matroids that does not follow from the common information property.
This is a joint work with Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, and Tamás Schwarcz, published in Proceeding of SODA 2026.
The paper is also available on https://arxiv.org/abs/2507.10709
Zoom session: https://cnrs.zoom.us/j/94897831760?pwd=7HoUVGcwLLlNCKm6gvuhh2b8JBuTKJ.1
Meeting ID: 948 9783 1760
Passcode: 9eUga3
The next meeting of the seminar AAIT is scheduled on March 11 (Wednesday), at 17h00 of Paris time (see https://time.is/CET).
Our speaker is Carles Padró (Universitat Politècnica de Catalunya).
Talk title: "Interaction between skew-representability, tensor products, extension properties, and rank inequalities."
Abstract: Skew-representable matroids form a fundamental class in matroid theory, bridging combinatorics and linear algebra. They play an important role in areas such as coding theory, optimization, and combinatorial geometry, where linear structure is crucial for both theoretical insights and algorithmic applications. Since deciding skew-representability is computationally intractable, much effort has been focused on identifying necessary or sufficient conditions for a matroid to be skew-representable.
In this paper, we introduce a novel approach to studying skew-representability and structural properties of matroids and polymatroid functions via tensor products. We provide a characterization of skew-representable matroids, as well as of those representable over skew fields of a given prime characteristic, in terms of tensor products. As an algorithmic consequence, we show that deciding skew-representability, or representability over a skew field of fixed prime characteristic, is co-recursively enumerable: that is, certificates of non-skew-representability — in general or over a fixed prime characteristic — can be verified. We also prove that every rank-3 matroid admits a tensor product with any uniform matroid and give a construction yielding the unique freest tensor product in this setting. Finally, as an application of the tensor product framework, we give a new proof of Ingleton's inequality and, more importantly, derive the first known linear rank inequality for folded skew-representable matroids that does not follow from the common information property.
This is a joint work with Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, and Tamás Schwarcz, published in Proceeding of SODA 2026.
The paper is also available on https://arxiv.org/abs/2507.10709
Zoom session: https://cnrs.zoom.us/j/94897831760?pwd=7HoUVGcwLLlNCKm6gvuhh2b8JBuTKJ.1
Meeting ID: 948 9783 1760
Passcode: 9eUga3
Reply all
Reply to author
Forward
0 new messages