Gil Kalai

Gil Kalai (hebräisch ‏גיל קלעי‎; * 1955 in Tel Aviv) ist ein israelischer Mathematiker und Informatiker, der sich mit Algorithmen zum Beispiel der Linearen Programmierung und Kombinatorik beschäftigt.

Gil Kalai 1986

Kalai promovierte 1983 an der Hebrew University bei Micha Perles und war danach als Post-Doc am Massachusetts Institute of Technology. Ab 1985 war er an der Hebrew University, wo er 1993 eine volle Professur erhielt. Gleichzeitig ist er Adjunct Professor für Informatik und Mathematik an der Yale University. 1994 war er Milliman Lecturer an der University of Washington. Er war unter anderem Gastwissenschaftler und Gastprofessor am Institute for Advanced Study (1995) und bei IBM in San Jose (1991/92).

Er ist Herausgeber des Israel Journal of Mathematics. 1992 erhielt er den Pólya-Preis der SIAM, 1993 den Erdös-Preis der israelischen mathematischen Gesellschaft, 1994 den Fulkerson-Preis. 1994 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Zürich (Combinatorics and convexity).

Kalai ist bekannt dafür, dass er Varianten des Simplex-Algorithmus fand, die in subexponentieller Zeit laufen.^[1]. Mit Ehud Friedgut bewies er 1996, das jede monotone Eigenschaft von Graphen einen scharfen Phasenübergang besitzt (bei Variation der Größe des Graphen, der Anzahl der Knoten).^[2]. 1993 widerlegte er mit Jeff Kahn eine Vermutung von Karol Borsuk über die Anzahl der Teile f(d) (als Funktion der Dimension d), die nötig sind, um konvexe Mengen im $\mathbb R^d$ in Teilmengen mit kleinerem Durchmesser zu zerlegen.^[3]. Borsuk vermutete f(d) = d + 1, Kalai und Kahn bewiesen $f(d) \geq (1{,}2)^{\sqrt d}$ für große d.

Gil Kalai 2007 in Oberwolfach

Weblinks

• Homepage
• Sein Blog „Combinatorics and more“
• Biografie an der Universität Eindhoven

Einzelnachweise

1. ↑ Kalai A subexponential randomized simplex algorithm“, Proc. 24. ACM Symposium on the Theory of Computing (STOC) 1992, S.475-482
2. ↑ Friedgut, Kalai, Every monotone graph property has a sharp threshold , Proceedings AMS, Bd.124, 1996, S.2993
3. ↑ Kahn, Kalai, "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society, Bd.29, 1993, S.60-62.

Normdaten: PND: 122009428 (PICA) | LCCN: n94077090 | VIAF: 19856707 | WorldCat | WP-Personeninfo