Gil Kalai

Un article de Wikipédia, l'encyclopédie libre.
Gil Kalai
Image dans Infobox.
Gil Kalai en 2007 à Oberwolfach
Biographie
Naissance
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Domaines
Membre de
Directeur de thèse
Distinction
Prix Erdős ()Voir et modifier les données sur Wikidata
Gil Kalai en 1986

Gil Kalai (en hébreu : גיל קלעי, 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[modifier | modifier le code]

Kalai soutient une thèse en 1983 à l’université hébraïque de Jérusalem sous la direction de Micha Perles[1] ; 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[2]. 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[modifier | modifier le code]

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[3]. Il est élu membre honoraire de l’Académie hongroise des sciences en [4]. En 2016, il délivre une conférence plénière au European Congress of Mathematics (Combinatorics of boolean functions and more)[5].

Travaux[modifier | modifier le code]

Kalai est connu pour avoir trouvé des variantes de l'algorithme du simplexe qui opèrent en temps sous-exponentiel[6]. 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[7]. Avec Jeffe Kahn, il donne en 1993 un contre-exemple à une conjecture de Borsuk (de) 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[8]. Borsuk conjecturait , Kalai et Kahn démontrent que pour assez grand. Kalai a également travaillé sur la conjecture de Hirsch[9].

La conjecture de Kalai[10] 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[11] attire une large attention médiatique.

Notes et références[modifier | modifier le code]

  1. (en) « Gil Kalai », sur le site du Mathematics Genealogy Project.
  2. Page de Kalai à Yale « Copie archivée » (version du 23 juillet 2018 sur l'Internet Archive).
  3. Yad Hanadiv, Rothschild Prize.
  4. L'académie hongroise des sciences a élu de nouveaux membres.
  5. Liste des conférences plénières des congrès européens de mathématiques, Berlin 2016.
  6. Gil Kalai, « A subexponential randomized simplex algorithm », Proc. 24th ACM Symp. Theory of Computing (STOC 1992),‎ , p. 475–482.
  7. (en) Ehud Friedgut et Gil Kalai, « Every monotone graph property has a sharp threshold », Proceedings of the American Mathematical Society, vol. 124, no 10,‎ , p. 2993–3003 (ISSN 0002-9939, DOI 10.1090/S0002-9939-96-03732-X, lire en ligne)
  8. (en) Jeff Kahn et Gil Kalai, « A Counterexample to Borsuk's Conjecture », Bulletin of the American Mathematical Society, vol. 29, no 1,‎ , p. 60–63 (ISSN 0273-0979, DOI 10.1090/S0273-0979-1993-00398-7).
  9. (en) Gil Kalai et Daniel J. Kleitman, « A quasi-polynomial bound for the diameter of graphs of polyhedra », Bulletin of the American Mathematical Society, vol. 26, no 2,‎ , p. 315–317 (ISSN 0273-0979, DOI 10.1090/S0273-0979-1992-00285-9, Math Reviews 1130448, arXiv math/9204233, lire en ligne).
  10. (en) Gil Kalai, « The number of faces of centrally-symmetric polytopes », Graphs and Combinatorics, vol. 5, no 1,‎ , p. 389–391 (ISSN 0911-0119, DOI 10.1007/BF01788696).
  11. (en) Gil Kalai, « How Quantum Computers Fail », Arxiv,‎ (lire en ligne)

Liens externes[modifier | modifier le code]