Lyon Information and Complexity Seminar

This working group aims to bring together mathematicians and computer scientists from Université de Lyon to collaborate on topics related to the foundations of information theory and its applications.

Talks are usually held either on Tuesday or Friday at 10:15am at ENS Lyon. The format of the talks is a general 45 minute talk followed by a more detailed discussions for those who are interested. Please contact one of the organizers Guillaume Aubrun (Lyon 1) or Omar Fawzi (ENS Lyon) if you would like to give a talk.

We also currently have a reading group on lower bounds for SDP relaxations.

Upcoming talks

  • Title: Quantum Expander Codes
    Time & Place: June, 14th at 11:00 in Salle B1
    Speaker: Anthony Leverrier (Inria Paris)
    Abstract: We present an efficient decoding algorithm for constant rate quantum hypergraph-product LDPC codes which provably corrects adversarial errors of weight \Omega(\sqrt{n}) for codes of length n. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from. (Joint work with Jean-Pierre Tillich and Gilles Zémor)

Past talks

  • Title: Equivariant semidefinite lifts and sum-of-squares hierarchies
    Time & Place: May 17th at 10:15 in Salle B2
    Speaker: Hamza Fawzi (MIT)
    Abstract: A polytope P has a positive semidefinite lift (psd lift) of size d if it can be expressed as the projection of the affine slice of the dxd positive semidefinite cone. In this work we study a class of semidefinite programming lifts that respect symmetries, so-called equivariant semidefinite lifts, and show how they relate to certain sum-of-squares certificates of the facet inequalities that capture the corresponding symmetries. We use this connection to derive lower bounds on the size equivariant semidefinite lifts for certain families of polytopes (cut polytope, parity polytope, regular polygons).
  • Title: Matrices de corrélations aléatoires: quand sont-elles avec grande probabilité classiques ou quantiques?
    Time & Place: Tuesday, May 3rd at 10:15 in Amphi K
    Speaker: Cecilia Lancien (Lyon 1)
    Abstract: Deux observateurs effectuant des mesures binaires sur des sous-parties d'un système global peuvent obtenir des résultats plus fortement corrélés lorsqu'ils partagent un état quantique intriqué que lorsqu'ils ne partagent que de l'aléa commun. Ce phénomène bien connu, dit de violation d'inégalités de Bell, peut précisément se caractériser mathématiquement. En effet, être une matrice de corrélations classique ou quantique correspond exactement à être dans la boule unité de certaines normes tensorielles. Je commencerai par expliquer tout cela en détail. Ensuite, je m'intéresserai au problème suivant: étant donnée une matrice aléatoire de taille n, peut-on estimer la valeur typique de ses normes "classique" et "quantique", lorsque n devient grand? Pour une large classe de matrices aléatoires, la réponse est oui, et montre une séparation entre les deux valeurs. Ce résultat peut s'interpréter de la façon suivante: dans une direction typique, les frontières des ensembles de corrélations classique et quantique ne se touchent pas, ou encore: dans une direction typique, les ensembles duaux des ensembles de corrélations classique et quantique ont des largeurs différentes.
  • Title: On qubit-qudit entanglement: normal extensions and positive biquadratic forms
    Time & Place: Wednesday, March 16th at 14:00 in salle 125 - 1 étage - Braconnier (Lyon 1)
    Speaker: Ion Nechita (Toulouse)
  • Title: Quantum information and the round complexity of disjointness
    Time & Place: Friday, February 19th at 10:15 in Amphi L
    Speaker: Ankit Garg (Princeton)
    Abstract: I will give an overview of quantum information complexity, a notion recently introduced by Touchette. It holds the promise of helping tackle direct sum and direct product questions for quantum communication complexity. As an application, I will describe a recent result on the optimal round-communication tradeoffs for the quantum communication complexity of disjointness. The result on disjointness is joint work with Mark Braverman, Young Kun Ko, Jieming Mao and Dave Touchette.
  • Title: Dvoretzky's theorem and the complexity of entanglement detection
    Time & Place: Wednesday, December 16th at 10:15 in Amphi J
    Speaker: Guillaume Aubrun (Lyon 1)
    Abstract: Dans un premier temps, je présenterai une inégalité fondamentale due à Figiel-Lindenstrauss-Milman (1977) sur la complexité des ensembles convexes de grande dimension (dans le cas des polytopes cette inégalité relie le nombre de sommets, le nombre de faces, et le rayon des boules inscrite et circonscrite). Dans un second temps je ferai le lien avec la complexité de l'intrication: en particulier, je montrerai que le nombre d'applications positives sur l'algèbre des matrices dxd nécessaires pour détecter tous les états intriqués sur C^d \otimes C^d est au moins exp(cd^3/log d).
  • Title: Entropy accumulation
    Time & Place: Wednesday, December 2nd at 10:15 in Salle 116
    Speaker: Frédéric Dupuis (Masaryk)
    Abstract: We ask the question whether entropy accumulates, in the sense that the opera- tionally relevant total uncertainty about an n-partite system A = (A1, . . . An) can be seen as the sum of the entropies of its parts Ai. The well-known Asymptotic Equipartition Property implies that this is indeed the case asymptotically for large n, under the assumption that the individual parts Ai are identical and independent of each other. Here we show that entropy accumulation occurs more generally, i.e., without an independence assumption, provided one quantifies the uncertainty about the individual systems Ai by the von Neumann entropy of suitably chosen conditional states. This result has a number of applications as it allows to reduce the analysis of a large system to the study of its parts. We also present some sample applications of the result by giving a security proof of a Quantum Key Distribution protocol, and an upper bound on the fidelity of fully quantum random access codes.
  • Title: Quantum Coding with Finite Resources
    Time & Place: Wednesday, November 18th at 10:15 in Amphi J (ENS Lyon, ground floor)
    Speaker: Mario Berta (Caltech)
    Abstract: The quantum capacity of a memoryless channel determines the maximal rate at which we can code reliably over asymptotically many uses of the channel. Here we argue that this asymptotic characterization is often insufficient in practice where decoherence severely limits our ability to manipulate large quantum systems in the encoder and decoder. For all practical purposes we should instead focus on the optimal trade-off between three parameters: the rate of the code, the size of the quantum devices at the encoder and decoder, and the fidelity of the transmission. Towards this goal, we find approximate and exact characterizations of this tradeoff for various channels, including dephasing, depolarizing and erasure channels. In each case the tradeoff is parametrized by the capacity and a second channel parameter, the quantum channel dispersion. In the process we develop several general bounds that are valid for all finite-dimensional quantum channels and can be computed efficiently. This is joint work with Marco Tomamichel and Joseph M. Renes (arXiv:1504.04617).


We acknowledge funding by Labex MILYON, Institut Camille Jordan and Laboratoire de l'Informatique du Parallélisme.