Lauréat 2018 du prix de mathématiques André-Aisenstadt
Ben Rossman (Université of Toronto)
[ English ]
La conférence de Benjamin Rossman (University of Toronto) aura lieu le 2 novembre dans la salle 1355 du Pavillon André-Aisenstadt.
Vendredi 2 novembre 2018
Centre de recherches mathématiques
Pavillon André-Aisenstadt
Université de Montréal
Salle 1355
16:00 - 17:00
Diaporama de la conférence
Vidéo de la conférence
The complexity of detecting cliques and cycles in random graphs
A strong form of the P ≠ NP conjecture holds that no algorithm faster than n^{O(k)} solves the k-clique problem with high probability when the input is an Erdös–Rényi random graph with an appropriate edge density. Toward this conjecture, I will describe a line of work lower-bounding the average-case complexity of k-clique (and other subgraph isomorphism problems) in weak models of computation: namely, restricted classes of boolean circuits and formulas. Along the way I will discuss some of the history and current frontiers in Circuit Complexity.
Joint work with Ken-ichi Kawarabayashi, Yuan Li and Alexander Razborov.
Une réception suivra la conférence au Salon Maurice-L’Abbé (salle 6245).
BIOGRAPHIE
Ben Rossman a obtenu son doctorat en 2010 au MIT sous la direction de Madhu Soudan. Ensuite il a été postdoctorant à l'université de technologie de Tokyo, à l'Institut Simons pour la théorie de l'informatique à Berkeley et à l'Institut national d'informatique de Tokyo avant de rejoindre l'Université de Toronto en 2016. Il est Sloan Fellow (2017) et conférencier invité au Congrès international des mathématiciens de Rio de Janeiro (2018).
Rossman travaille dans le domaine de la théorie de la complexité computationnelle, une branche de l'informatique théorique qui vise à comprendre les problèmes mathématiques et algorithmiques en fonction de leur difficulté relative. Ses recherches sont axées sur la quantification des ressources minimales requises pour résoudre des problèmes fondamentaux dans des modèles combinatoires tels que les circuits booléens. Grâce à des techniques créatives basées sur la logique et les méthodes probabilistes, Ben a obtenu des bornes inférieures révolutionnaires pour la complexité de la détection des cliques et la détermination de la connectivité dans les graphes aléatoires. Ses autres résultats notables incluent des théorèmes de hiérarchie de taille et de profondeur pour les circuits à profondeur bornée, résolvant des questions de longue date. Ce travail a contribué à un regain d'intérêt récent pour la recherche sur la complexité des circuits, en particulier avec une approche concrète à la conjecture "P vs NP" qui avait peu progressé depuis les percées des années 1980. À l'automne 201
|
