Gil Kalai

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

La conjecture ${\displaystyle 3^{d}}$ de Kalai^[10] stipule que tout polytope de dimension d à symétrie centrale possède au moins ${\displaystyle 3^{d}}$ « facettes » (où on compte les sommets, arêtes, faces, etc., et le polytope lui-même). Par exemple, pour ${\displaystyle d=2}$ et un parallélogramme, on a ${\displaystyle 4+4+1=9=3^{2}}$ et pour un cube avec ${\displaystyle d=3}$ on a ${\displaystyle 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.

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

• Ressources relatives à la recherche :
  • Digital Bibliography & Library Project
  • Google Scholar
  • Mathematics Genealogy Project
  • ORCID
• Notices d'autorité :

  • VIAF
  • ISNI
  • BnF (données)
  • IdRef
  • LCCN
  • GND
  • CiNii
  • Pays-Bas
  • Israël
  • NUKAT
  • Norvège

• Portail des mathématiques
• Portail de l'informatique théorique