Techniques algorithmiques pour les modèles de données à accès restreint – RDAM

Ce projet rassemble des chercheurs de différents domaines fondamentaux de l'informatique, et tire parti de leur expertise pour développer des outils de conception d'algorithmes et d'étude de la complexité des modèles de données à accès restreint. Certains outils seront adaptés de ceux existants, et d'autres seront créés.

1. Nous avons conçu le premier algorithme quantique pour les systèmes de recommandation fonctionnant en temps polylogarithmique dans les dimensions de la matrice et fournissant un exemple d'algorithme d'apprentissage quantique pour une application du monde réel (ITCS'17).
2. Nous avons établi plusieurs séparations optimales entre certaines mesures de la complexité des requêtes déterministes, randomisées et quantiques (STOC’16). Nos séparations ont notamment réfuté une hypothèse de Saks et Wigderson de 1986.
3. Nous avons formellement défini et étudié l’effet de plafond de verre dans les réseaux sociaux et proposé un modèle mathématique naturel, appelé modèle d’attachement préférentiel biaisé, qui explique en partie les causes de l’effet de plafond de verre (ITCS’15).
4. Combien faut-il couper pour simplifier la topologie d'une surface ? Nous fournissons des bornes pour plusieurs exemples importants de cette question (SOCG'14). Nous prouvons en particulier une conjecture de Przytycka et Przytycki de 1993.
5. Première mise en œuvre d'un protocole quantique pour le lancement de pièces, avec une sécurité inconditionnellement plus forte que dans n'importe quel protocole classique (Nature Communication 2014).

Les deux groupes de recherche impliqués dans ce projet ont de très bons antécédents de recherche fondamentale en informatique théorique. Dans le cadre de la recherche fondamentale, ils commencent à changer de perspective en fonction des nouvelles priorités énoncées dans cette proposition. Le but de ce projet est de soutenir cette évolution vers les nouvelles directions. Dans certaines de ces directions, ils sont déjà au niveau international. Dans les autres, l'objectif est d'atteindre ce niveau dans un court laps de temps.

Le projet a suscité 111 publications, dont 38 dans des revues internationales les plus prestigieuses, et 67 dans les actes de conférences internationales les plus réputées. A noter aussi 4 actions de diffusion grand public.

Ce projet vise à mieux comprendre la notion de calcul lorsque l'accès aux données d'entrée est restreint de diverses façons. Les scénarios conduisent à une nouvelle étude des notions habituelles de complexité telles que temps ou espace.
Comment traiter des quantités massives de données ? Les considérations de temps conduisent à des restrictions naturelles modélisées par des algorithmes en temps sous-linéaire. Les algorithmes en temps sous-linéaire, et parmi eux les testeurs de propriété, imposent une vue partielle de l'entrée. Ils sont intrinsèquement robustes face aux données corrompues. Les considérations d'espace conduisent à des restrictions naturelles modélisées par des algorithmes de streaming, et plus généralement des algorithmes à mémoire externe, dont la mémoire interne est sous-linéaire et l'accès aux données d'entrée séquentiel. Dans certains cas, la complexité de la communication peut fournir des outils essentiels pour établir des résultats d'impossibilité.
Comment traiter avec des vues partielles de données privées révélées à la discrétion de leurs propriétaires ? L'accès aux données peut également être restreint dans le sens où l'entrée considérée par l'algorithme peut ne pas être la "vraie" entrée. La théorie des jeux fournit un modèle pour la conception d'algorithmes dans ce contexte, qui peut aussi être étendu afin d'y intégrer des préoccupations de confidentialité. La théorie des jeux quantique peut alors fournir parfois des outils pour prouver des résultats d'impossibilité.
Comment traiter les données d'un réseau en perpétuelle évolution ? Au lieu de voir ces changements comme des contraintes pour adapter nos algorithmes, ils peuvent être utilisés comme des leviers qui permettent de mieux mettre en relief les véritables structures sous-jacentes.
Ce projet rassemble des chercheurs de différents domaines fondamentaux de l'informatique, et tire parti de leur expertise pour développer des outils de conception d'algorithmes et d'étude de la complexité des modèles de données à accès restreint. Certains outils seront adaptés de ceux existants, et d'autres seront créés.