Thème abordés par le séminaire « Information et Complexité » 2015-2016

Le groupe de travail  de ce séminaire s’articule autour de deux axes concernant la théorie de l’information :

  • Le développement de méthodes mathématiques pour l’étude de problèmes fondamentaux de traitement de l’information. Dans les cinq dernières années, des outils de convexité en grande dimension se sont avérés essentiels pour analyser diverses propriétés des canaux quantiques, en particulier la capacité classique [2] (voire aussi le livre en préparation [1]). La théorie des espaces d’opérateurs a également été appliquée à la construction d’inégalités de Bell [7] ainsi que pour des preuves de sécurité d’extracteurs d’aléa [3].

L’objectif est d’exploiter ces connexions de manière plus approfondie et de trouver des nouvelles applications à d’autres problèmes liés au traitement de l’information.

  1. Le point de vue de la théorie de l’information a joué un rôle majeur dans des développements récents en informatique théorique En particulier, le domaine de complexité en information (”information complexity”) utilise les propriétés des règles de chaînage des quantités entropiques pour obtenir des résultats en complexité de la communication [5,8] mais également pour prouver des bornes inférieures sur la représentation de problèmes d’optimisation combinatoire [6]. Les règles de chainage de l’entropie ont également donné des preuves très élégantes pour des théorèmes de type “de Finetti” qui trouvent des applications en complexité quantique [4]. En combinatoire, une méthode dite de “entropy compression” a été utilisée pour donner une preuve constructive du théorème local de Lovasz [9].

L’objectif est d’abord de se familiariser avec ces diverses applications pour pouvoir contribuer à ces problématiques.

 

Références

[1]G. Aubrun and S. Szarek.   Alice and Bob meet Banach. The Interface of Asymptotic Geometric Analysis and Quantum Information Theory. In preparation.

[2]G. Aubrun, S. Szarek, and E. Werner. Hastings’s Additivity Counterexample via Dvoret- zky’s Theorem. Comm. Math. Phys., 305:85–97, 2011. arXiv:1003.4925.

[3]M. Berta, O. Fawzi, and V. Scholz. Quantum-proof randomness extractors via operator space theory. arXiv preprint arXiv:1409.3563, 2014.

[4]F. Brand˜ao and A. Harrow. Quantum de Finetti theorems under local measurements with applications. In Proc. ACM STOC, pages 861–870. ACM, 2013.arXiv:1210.6367.

[5]M. Braverman. Interactive information complexity. In Proc. ACM STOC, pages 505–524.

ACM, 2012.ECCC:TR11-123.

[6]M. Braverman and A. Moitra. An information complexity approach to extended formu- lations. In Proc. ACM STOC, pages 161–170. ACM, 2013.

[7]M. Junge, C. Palazuelos, D. P´erez-Garc´ıa, I. Villanueva, and M. M. Wolf. Operator space theory: a natural framework for bell inequalities. Phys. Rev. Lett., 104(17):170405, 2010.

[8]I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. Lower bounds on infor- mation complexity via zero-communication protocols and applications. In Proc. FOCS, pages 500–509. IEEE, 2012.arXiv:1204.1505.

[9]R. A. Moser and G. Tardos. A constructive proof of the general lov A´ sz local lemma. J. ACM, 57(2):11:1–11:15, Feb. 2010.