Gil Kalai (en , 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 sciencesYad Hanadiv, Rothschild Prize.. Il est élu membre honoraire de l’Académie hongroise des sciences en L'académie hongroise des sciences a élu de nouveaux membres.. En 2016, il délivre une conférence plénière au European Congress of Mathematics (Combinatorics of boolean functions and more)Liste des conférences plénières des congrès européens de mathématiques, Berlin 2016..
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 sur le nombre (comme fonction de la dimension ) de parties nécessaires pour décomposer des ensembles convexes de en parties de diamètre plus petit. Borsuk conjecturait , Kalai et Kahn démontrent que pour assez grand. Kalai a également travaillé sur la conjecture de Hirsch.
La conjecture de Kalai stipule que tout polytope de dimension d à symétrie centrale possède au moins « facettes » (où on compte les sommets, arêtes, faces, etc., et le polytope lui-même). Par exemple, pour et un parallélogramme, on a et pour un cube avec on a . 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.
Notes et références
Liens externes Page personnelle à l'université hébraïque Blog Combinatorics and more
Catégorie:Informaticien Catégorie:Naissance en octobre 1955 Catégorie:Lauréat du prix Erdős Catégorie:Lauréat du prix Fulkerson Catégorie:Lauréat du prix Georges-Polya Catégorie:Membre de l'Academia Europaea Catégorie:Membre de l'Académie hongroise des sciences Catégorie:Mathématicien israélien du XXe siècle Catégorie:Mathématicien israélien du XXIe siècle