Agenda de l'ENS de Lyon

Asymptotic properties of hypergraphs and channels

lun 11 juil 2022

10 heures


Amphi B


Soutenance de thèse de M. TA Duy-Hoang sous la direction de thèse de M. FAWZI Omar

Langue(s) des interventions
Description générale

Understanding the properties of objects under a natural product operation is a central theme in mathematics, computer science and physics. Examples of such basic objects include noisy communication channels in information theory, computational problems in algebraic complexity, and graphs in discrete mathematics. In this PhD thesis, we study the asymptotic growth of relevant properties for the powers of such objects.

The first objects we consider are hypergraphs equipped with the strong product operation and the property of interest is the independence number. The asymptotic growth of the independence number of a hypergraph is known as the Shannon capacity. We introduce a general method for lower bounding the Shannon capacity of hypergraphs via combinatorial degenerations, a notion which originates from the study of matrix multiplication in algebraic complexity theory. This allows us to obtain the best-known lower bounds for multiple combinatorial problems, including the corner problem and its application in communication complexity.

Tensors are the second considered objects. We can equip them with the tensor product and the property of interest is the symmetric subrank. The symmetric subrank is a notion we introduce motivated by limitations of current tensor methods to bound the Shannon capacity of hypergraphs. We prove precise relations and separations between subrank and symmetric subrank. We also prove that for symmetric tensors, the subrank and the symmetric subrank are asymptotically equal. This proves the asymptotic subrank analogon of a conjecture known as Comon’s conjecture in the theory of tensors.

Finally, we study the growth of the divergence between tensor powers of quantum channels. By exploiting symmetries, we propose efficient algorithms to approximate the asymptotic channel divergence between channels. As an application, we obtain improved bounds on quantum channel capacities.


Mots clés