Information and Complexity Day, Lyon 2016

This small workshop is about the mathematical aspects of quantum or classical information theory.

Location and time

November 14th and 15th, 2016 at ENS de Lyon

Getting to ENS Lyon

For the first day, the talks are in the third floor of the ENS-Lyon main building, see here for instructions.

For the second day, the talks are in the nearby Université Lyon I, see again here for instructions.

Schedule

Monday, November 14th

Morning: General session in Amphi B in ENS Lyon main building (called site Monod)

10:15 - 11:15 Monique Laurent (CWI): Completely positive semidefinite matrices and their applications
11:00 - 11:30 -- break --
11:45 - 12:45 Carlos Palazuelos (Universidad Complutense de Madrid): Quantum channels and operator spaces

Lunch break

Afternoon: Quantum Information Theory session in Salle du conseil (right next to Amphi B)

14:15 - 14:45 Frederic Grosshans (CNRS, Paris): Ambiguity-Losses Trade-Off for State Discrimination
14:45 - 15:15 Alex Grilo (IRIF, Paris): Pointer Quantum PCPs and Multi-Prover Games
15:15 - 15:45 -- break --
15:45 - 16:15 Mario Berta (Caltech): Deconstruction and conditional erasure of quantum correlations
16:15 - 16:45 Volkher Scholz (Ghent University): Quantum Bilinear Optimization

19:00 Dinner at Tandoor et Wok, 18 Rue Clément Marot, 69007 Lyon.

Tuesday, November 15th

Tuesday: Combinatorial optimization session in LUG meeting room in Université Lyon I building.

10:15 - 11:15 Samuel Fiorini (Université Libre de Bruxelles): Information theory and extended formulations

Lunch break

13:30 - 14:30 Tony Huynh (Université Libre de Bruxelles): Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank
14:30 - 16:00 Time for other talks/discussions

Abstracts

Monique Laurent (CWI): Completely positive semidefinite matrices and their applications
We consider completely positive semidefinite matrices, which are defined as those symmetric matrices that admit a Gram representation by positive semidefinite matrices (of any size). They form the completely positive semidefinite cone, which is nested between the completely positive cone (consisting of the matrices having a Gram representation by nonnegative vectors) and the doubly-nonnegative cone (consisting of the nonnegative matrices having a Gram representation by arbitrary vectors). We will discuss properties of this new matrix cone, hierarchies of inner and outer approximations, and applications in quantum information to express quantum graph parameters.

Carlos Palazuelos (Universidad Complutense de Madrid): Quantum channels and operator spaces
In this talk we will explain some connections between quantum channels and operator spaces. We will see that some well-known capacities of channels can be obtained by differentiating certain norms defined in the category of operator spaces. This will lead us to some questions about the use of assisted-entanglement in communication processes.

Frederic Grosshans (CNRS, Paris): Ambiguity-Losses Trade-Off for State Discrimination
Given a set of non-orthogonal linearly independent quantum states, unambiguous discrimination is only possible at the price of some losses. On the other hand the ambiguity of a lossless measurement can be evaluated by different figure of merits, depending on the application. Many of these figure of merits can be mapped to conditional α-Rényi entropies. Using their parent quantitity — th α-z-relative Rényi entropy D_{α,z}(ρ‖σ) introduced by Audenaert and Datta — we find here, for a set of equally likely symmetric states, the minimal value of these conditional entropies as a function of losses.

Alex Grilo (IRIF, Paris): Pointer Quantum PCPs and Multi-Prover Games
https://arxiv.org/abs/1603.00903

Mario Berta (Caltech): Deconstruction and conditional erasure of quantum correlations
https://arxiv.org/abs/1609.06994

Volkher Scholz (Ghent University): Quantum Bilinear Optimization
https://arxiv.org/abs/1506.08810

Samuel Fiorini (Université Libre de Bruxelles): Information theory and extended formulations
This talk is meant as an invitation to extended formulations, in particular to information theoretic techniques applied to extension complexity. Starting with Yannakakis' factorization theorem (1991), I will motivate two distinct lower bounds: the hyperplane separation bound, and common information (an information theoretic measure due to Wyner 1975), and explain how one can apply them to the Unique DISJointness (partial) matrix. If time permits, I will state a few interesting open problems in the area.

Tony Huynh (Université Libre de Bruxelles): Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank
Let $P$ be a polytope contained in $[0,1]^n$, $X$ be the set of 0/1-vectors not in $P$, and $H[X]$ be the subgraph of the $n$-cube induced by the vertices in $X$. We are interested in whether properties of the graph $H[X]$ tell us anything about the polytope $P$. The relevant parameter seems to be the 'pitch' of $H[X]$, which is the maximum $d$ such that $H[X]$ contains a $d$-dimensional subcube. Our main result is that if $H[X]$ has bounded pitch and $P$ has bounded facet coefficients, then the Chvátal-Gomory rank (CG-rank) of $P$ is bounded.
As corollaries, we obtain two different generalizations of a recent theorem of Cornuéjols and Lee, who proved that if $H[X]$ has treewidth at most 2, then the CG-rank of $P$ is bounded. Our results imply that the CG-rank of $P$ is always bounded as a function of the treewidth of $H[X]$. We also prove that if $H[X]$ has pitch at most 2, then the CG-rank of $P$ is bounded. Treewidth at most 2 implies pitch at most 2, but not vice versa.
Finally, we complement these results by proving that $P$ admits an extended formulation whose size is bounded by a function of the pitch of $H[X] $ and the depth of any circuit deciding membership in the vertex set of $P$. Our bound is polynomial whenever the pitch is constant and the depth is logarithmic.
This is joint work with Yohann Benchetrit, Samuel Fiorini, and Stefan Weltge.

Contact: omar.fawzi -at- ens-lyon.fr.