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.

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.^[1] 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). 2015 wurde er in die Academia Europaea und 2016 in die Israelische Akademie der Wissenschaften gewählt. 2016 hielt er einen Plenarvortrag auf dem Europäischen Mathematikerkongress (Combinatorics of boolean functions and more). 2018 war er Plenarsprecher auf dem ICM in Rio (Three Puzzles on Mathematics, Computation, and Games).^[2]

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

Die ${\displaystyle 3^{d}}$-Vermutung von Kalai^[6] besagt, dass jedes d-dimensionale zentralsymmetrische Polytop mindestens ${\displaystyle 3^{d}}$ Seiten hat (wobei Ecken, Kanten, Seitenflächen, … und auch das gesamte Polytop als Seiten mitgezählt werden). Zum Beispiel gilt in ${\displaystyle d=2}$ für das Parallelogramm ${\displaystyle 4+4+1=9=3^{2}}$ und für den Kubus in ${\displaystyle d=3}$ gilt ${\displaystyle 8+12+6+1=27=3^{3}}$. Der allgemeine Fall ist offen (in vier und weniger Dimensionen ist die Vermutung bewiesen, ebenso für simpliziale Polytope).

Er ist pessimistisch bezüglich der Realisierbarkeit von Quantencomputern.^[7][2]

• Homepage
• Gil Kalai im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
• Sein Blog Combinatorics and more
• Gil Kalai in der Datenbank zbMATH

1. ↑ 5-day minicourse on (i) the Combinatorics of Convex Polytopes and the Simplex Algorithm, (ii) The Cube (MC-DAG-7). TU Eindhoven, 2000, archiviert vom Original; abgerufen am 8. Juni 2011 (englisch). 
2. ↑ ^{a b} Gil Kalai: Three Puzzles on Mathematics, Computation, and Games. 8. Januar 2018, arxiv:1801.02602. 
3. ↑ Gil Kalai: A subexponential randomized simplex algorithm (extended abstract). In: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92. ACM Press, Victoria, British Columbia, Canada 1992, ISBN 978-0-89791-511-3, S. 475–482, doi:10.1145/129712.129759 (acm.org [abgerufen am 2. August 2020]). 
4. ↑ Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold. In: Proceedings of the American Mathematical Society. Band 124, Nr. 10, 1996, ISSN 0002-9939, S. 2993–3002, doi:10.1090/S0002-9939-96-03732-X (ams.org [abgerufen am 2. August 2020]). 
5. ↑ Jeff Kahn, Gil Kalai: A counterexample to Borsuk’s conjecture. In: Bulletin of the American Mathematical Society. Band 29, Nr. 1, 1993, ISSN 0273-0979, S. 60–62, doi:10.1090/S0273-0979-1993-00398-7, arxiv:math/9307229 (ams.org [abgerufen am 2. August 2020]). 
6. ↑ Gil Kalai: The number of faces of centrally-symmetric polytopes. In: Graphs and Combinatorics. Band 5, Nr. 1, 1. Dezember 1989, ISSN 1435-5914, S. 389–391, doi:10.1007/BF01788696. 
7. ↑ Gil Kalai: The Quantum Computer Puzzle (Expanded Version). 3. Mai 2016, arxiv:1605.00992.