Gil Kalai

Gil Kalai 2007 in Oberwolfach

Gil Kalai 1986

Gil Kalai ( Hebrew גיל קלעי; * 1955 in Tel Aviv ) is an Israeli mathematician and computer scientist who deals with algorithms such as linear programming and combinatorics .

Life

Kalai received his PhD from Hebrew University in 1983 with Micha Perles and was then a post-doc at the Massachusetts Institute of Technology . From 1985 he was at the Hebrew University, where he received a full professorship in 1993. He is also an adjunct professor of computer science and mathematics at Yale University . In 1994 he was a Milliman Lecturer at the University of Washington . Among other things, he was visiting scholar and visiting professor at the Institute for Advanced Study (1995) and at IBM in San Jose (1991/92).

He is editor of the Israel Journal of Mathematics. In 1992 he was awarded the SIAM Pólya Prize , the Erdős Prize of the Israeli Mathematical Society in 1993, and the Fulkerson Prize in 1994 . In 1994 he was invited speaker at the International Congress of Mathematicians in Zurich (Combinatorics and convexity). In 2015 he was elected to the Academia Europaea . In 2016 he gave a plenary lecture at the European Congress of Mathematicians (Combinatorics of boolean functions and more). In 2018 he was plenary speaker at the ICM in Rio (Three Puzzles on Mathematics, Computation, and Games).

Act

Kalai is known for finding variants of the simplex algorithm that run in sub-exponential time. With Ehud Friedgut in 1996 he proved that every monotonic property of graphs has a sharp phase transition (with variation of the size of the graph, the number of nodes). In 1993, together with Jeff Kahn, he refuted a conjecture made by Karol Borsuk about the number of parts (as a function of dimension ) that are necessary to split convex sets into subsets with a smaller diameter. Borsuk guessed , Kalai and Kahn proved sufficiently large . ${\ displaystyle f (d)}$ ${\ displaystyle d}$ ${\ displaystyle \ mathbb {R} ^ {d}}$ ${\ displaystyle f (d) = d + 1}$ ${\ displaystyle f (d) \ geq 1 {,} 2 ^ {\ sqrt {d}}}$ ${\ displaystyle d}$

The presumption of Kalai says that any d-dimensional centrally symmetric polytope least sides has (wherein vertices, edges, faces, ... and also the entire polytope are counted as pages). For example, in applies to the parallelogram and in applies to the cube . The general case is open (the conjecture is proven in four and fewer dimensions, as well as for simplicial polytopes). ${\ displaystyle 3 ^ {d}}$ ${\ displaystyle 3 ^ {d}}$ ${\ displaystyle d = 2}$ ${\ displaystyle 4 + 4 + 1 = 9 = 3 ^ {2}}$ ${\ displaystyle d = 3}$ ${\ displaystyle 8 + 12 + 6 + 1 = 27 = 3 ^ {3}}$

He is pessimistic about the feasibility of quantum computers.

Web links

Individual evidence

↑ 5-day mini course on (i) the Combinatorics of convex polytope and the Simplex Algorithm, (ii) The Cube (MC-DAG-7). TU Eindhoven, 2000, archived from the original ; accessed on June 8, 2011 .
^ ^A ^b Gil Kalai: Three Puzzles on Mathematics, Computation, and Games . January 8, 2018, arxiv : 1801.02602 .
^ 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 , pp. 475-482 , doi : 10.1145 / 129712.129759 ( acm.org [accessed August 2, 2020]).
↑ Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold . In: Proceedings of the American Mathematical Society . tape 124 , no. 10 , 1996, ISSN 0002-9939 , pp. 2993-3002 , doi : 10.1090 / S0002-9939-96-03732-X ( ams.org [accessed August 2, 2020]).
↑ Jeff Kahn, Gil Kalai: A counterexample to Borsuk's conjecture . In: Bulletin of the American Mathematical Society . tape 29 , no. 1 , 1993, ISSN 0273-0979 , pp. 60–62 , doi : 10.1090 / S0273-0979-1993-00398-7 , arxiv : math / 9307229 ( ams.org [accessed August 2, 2020]).
↑ Gil Kalai: The number of faces of centrally-symmetric polytopes . In: Graphs and Combinatorics . tape 5 , no. 1 , December 1, 1989, ISSN 1435-5914 , pp. 389-391 , doi : 10.1007 / BF01788696 .
↑ Gil Kalai: The Quantum Computer Puzzle (Expanded Version) . May 3, 2016, arxiv : 1605.00992 .

personal data
SURNAME	Kalai, Gil
BRIEF DESCRIPTION	Israeli mathematician
DATE OF BIRTH	1955
PLACE OF BIRTH	Tel Aviv

[1] 5-day mini course on (i) the Combinatorics of convex polytope and the Simplex Algorithm, (ii) The Cube (MC-DAG-7). TU Eindhoven, 2000, archived from the original ; accessed on June 8, 2011 .

[:0-2] A ^b Gil Kalai: Three Puzzles on Mathematics, Computation, and Games . January 8, 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 , pp. 475-482 , doi : 10.1145 / 129712.129759 ( acm.org [accessed August 2, 2020]).

[4] Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold . In: Proceedings of the American Mathematical Society . tape 124 , no. 10 , 1996, ISSN 0002-9939 , pp. 2993-3002 , doi : 10.1090 / S0002-9939-96-03732-X ( ams.org [accessed August 2, 2020]).

[5] Jeff Kahn, Gil Kalai: A counterexample to Borsuk's conjecture . In: Bulletin of the American Mathematical Society . tape 29 , no. 1 , 1993, ISSN 0273-0979 , pp. 60–62 , doi : 10.1090 / S0273-0979-1993-00398-7 , arxiv : math / 9307229 ( ams.org [accessed August 2, 2020]).

[6] Gil Kalai: The number of faces of centrally-symmetric polytopes . In: Graphs and Combinatorics . tape 5 , no. 1 , December 1, 1989, ISSN 1435-5914 , pp. 389-391 , doi : 10.1007 / BF01788696 .

[7] Gil Kalai: The Quantum Computer Puzzle (Expanded Version) . May 3, 2016, arxiv : 1605.00992 .