Gil Kalai

Biographie
Naissance	2 octobre 1955 (69 ans); Tel Aviv
Nationalité	israélienne
Formation	Université hébraïque de Jérusalem
Activités	Mathématicien, informaticien
A travaillé pour	Université Yale
Membre de	Academia Europaea (2015); American Mathematical Society (2022); Académie israélienne des sciences et lettres
Directeur de thèse	Micha Perles
Distinctions	Prix Erdős (1992); Membre honoraire de l'American Mathematical Society (2023)

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

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

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 mai 2016^[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

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 $f(d)$ (comme fonction de la dimension $d$ ) de parties nécessaires pour décomposer des ensembles convexes de $\mathbb {R} ^{d}$ en parties de diamètre plus petit^[8]. Borsuk conjecturait $f(d)=d+1$ , Kalai et Kahn démontrent que $f(d)\geq 1{,}2^{\sqrt {d}}$ pour $d$ assez grand. Kalai a également travaillé sur la conjecture de Hirsch^[9].

La conjecture $3^{d}$ de Kalai^[10] 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^[11] 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^[12].

Notes et références

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

Liens externes

Ressources relatives à la recherche :
- (en) Digital Bibliography & Library Project
- (en) Google Scholar
- (en) Mathematics Genealogy Project
- (en) ORCID
Notices d'autorité :
- VIAF
- ISNI
- BnF (données)
- IdRef
- LCCN
- GND
- CiNii
- Pays-Bas
- Israël
- NUKAT
- Norvège
- WorldCat

[1] (en) « Gil Kalai », sur le site du Mathematics Genealogy Project.

[yale-2] Page de Kalai à Yale « Copie archivée » (version du 23 juillet 2018 sur 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.

[Kalai1992-6] Gil Kalai, « A subexponential randomized simplex algorithm », Proc. 24th ACM Symp. Theory of Computing (STOC 1992),‎ 1992, p. 475–482.

[FriedgutKalai1996-7] (en) Ehud Friedgut et Gil Kalai, « Every monotone graph property has a sharp threshold », Proceedings of the American Mathematical Society, vol. 124, n^o 10,‎ 1996, p. 2993–3003 (ISSN 0002-9939, DOI 10.1090/S0002-9939-96-03732-X, lire en ligne)

[KahnKalai1993-8] (en) Jeff Kahn et Gil Kalai, « A Counterexample to Borsuk's Conjecture », Bulletin of the American Mathematical Society, vol. 29, n^o 1,‎ 1993, p. 60–63 (ISSN 0273-0979, DOI 10.1090/S0273-0979-1993-00398-7).

[KalaiKleitman1992-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, n^o 2,‎ 1992, p. 315–317 (ISSN 0273-0979, DOI 10.1090/S0273-0979-1992-00285-9, MR 1130448, arXiv math/9204233, lire en ligne).

[Kalai1989-10] (en) Gil Kalai, « The number of faces of centrally-symmetric polytopes », Graphs and Combinatorics, vol. 5, n^o 1,‎ 1989, p. 389–391 (ISSN 0911-0119, DOI 10.1007/BF01788696).

[11] (en) Gil Kalai, « How Quantum Computers Fail », Arxiv,‎ 2011 (lire en ligne)

[bruit-12] Article IT QSocial .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]