Gil Kalai

Gil Kalai en 1986

Gil Kalai (en Modèle:Lang-he, né en 1955 à Tel Aviv) est un mathématicien et informaticien israélien qui travaille en algorithmique, notamment en optimisation linéaire et en combinatoire.

Carrière

Kalai soutient une thèse en 1983 à l’université hébraïque de Jérusalem sous la direction de Micha Perles ; il est ensuite chercheur post-doc au Massachusetts Institute of Technology. À partir de 1985, il travaille à l'université hébraïque de Jérusalem, où il obtient un poste de professeur titulaire en 1993. En même temps, il est adjunct professor pour informatique et mathématiques à l'université Yale. En 1994, il est Milliman Lecturer à l'université de Washington. D'autre part, il est chercheur invité et professeur invité à l'Institute for Advanced Study (1995) et chez IBM à San Jose (1991-92).

Kalai est éditeur en chef du Israel Journal of Mathematics de 1995 à 2001.

Prix et distinctions

En 1992 il reçoit le prix Pólya (LMS) de la SIAM, en 1993 le prix Erdős de la société mathématique israélienne, en 1994 le prix Fulkerson. Kalai 1994 est un conférencier invité au Congrès international des mathématiciens à Zürich (Combinatorics and convexity). En 2015, il est élu membre de la Academia Europaea. En 2012, il reçoit le prix Rothschild en sciences. Il est élu membre honoraire de l’Académie hongroise des sciences en Modèle:Date-. En 2016, il délivre une conférence plénière au European Congress of Mathematics (Combinatorics of boolean functions and more).

Travaux

Kalai est connu pour avoir trouvé des variantes de l'algorithme du simplexe qui opèrent en temps sous-exponentiel. Avec Ehud Friedgut, il démontre en 1996 que toute propriété monotone de graphes possède un seuil exact en fonction de la variation du nombre de nœuds du graphe. Avec Jeffe Kahn, il donne en 1993 un contre-exemple à une Modèle:Lien sur le nombre $f(d)$ (comme fonction de la dimension $d$) de parties nécessaires pour décomposer des ensembles convexes de ${ℝ}^d$ en parties de diamètre plus petit. Borsuk conjecturait $f(d)=d+1$, Kalai et Kahn démontrent que $f(d)\ge 1,2^{\sqrt{d}}$ pour $d$ assez grand. Kalai a également travaillé sur la conjecture de Hirsch.

La conjecture $3^d$ de Kalai stipule que tout polytope de dimension d à symétrie centrale possède au moins $3^d$ « facettes » (où on compte les sommets, arêtes, faces, etc., et le polytope lui-même). Par exemple, pour $d=2$ et un parallélogramme, on a $4+4+1=9=3^2$ et pour un cube avec $d=3$ on a $8+12+6+1=27=3^3$. Le cas général est ouvert (la conjecture est démontrée pour les dimensions au plus 4, de même pour les polytopes simpliciaux).

En 2011, sa critique du calcul quantique attire une large attention médiatique. Il conjecture que l'ordinateur quantique ne marchera jamais du fait qu'en augmentant sa taille, l'augmentation simultanée du bruit quantique empêchera toute forme de mesure et que ce problème ne pourra pas être résolu, étant systémique au quantique. le « bruit quantique » est la sensibilité et la stabilité des superposition des qubits qui rendrait inévitable la corruption des interactions avec le monde extérieur. Plus précisément, le « bruit » c’est la probabilité que des erreurs affectent le résultat d’un processus. Pire, ce « bruit » violerait certains théorèmes fondamentaux du calcul, dont la théorie de l'informatique sur la puissance des dispositifs de calcul primitifs.

Liens externes

• Page personnelle à l'université hébraïque
• Blog Combinatorics and more