Gil Kalai
Adjunct Professor of Computer Science & Mathematics

Office Location: AKW 404
Telephone: 203.432.1238
Personal Homepage

Gil Kalai is an Adjuct Professor of Computer Science and Mathematics at Yale University. His research areas are Combinatorics and Convexity. He is interested in the combinatorial theory of convex polytopes, relations of combinatorics with topology and with Fourier analysis, Boolean functions, and threshold and isoperimetric phenomena. He is interested in applications to theoretical computer science, mathematical programming, probability theory and economics.

Here are a few problems he would like to understand himself or see solved by others:

1. Is there a polynomial variant of the simplex algorithm for linear programming? Is at least the diameter of graphs of polytopes at most polynomial in the dimension and number of facets?

2. What is the scope, strength and interpretation of threshold phenomena that we observe in combinatorics and in models from complexity theory, probability and economics.

3. Verify the "g-conjecture" concerning face numbers of triangulation of spheres.

4. In combinatorial optimization and question arising in discrete and computational geometry, when and why can we relate the integral optimum and its fractional relaxation? (This sounds vague and indeed it is.)

Kalai is the recipient of the 1992 Polya Prize, the 1993 Erdos Prize and the 1994 Fulkerson Prize. He is on the faculty of the Hebrew University of Jerusalem from 1985 where he is at present the Henry and Manya Noskwith Professor of Mathematics. He was a cofounder of the center for theoretical computer science and discrete mathematics at the Hebrew University. He serves in several scientific committees and editorial boards and was involved in committees concerning pension issues and concerning status of women in academics.

Representative Publications:
	J. Kahn, G. Kalai and N. Linial, The influence of variables on Boolean functions, Proc. 29-th Annual Symposium on Foundations of Computer Science, 68-80, Computer Society Press, 1988.
	A. Bjorner and G. Kalai, An extended Euler-Poincare formula, Acta Math. 161 (1988), 279-303.
	J. Kahn and G. Kalai, A counterexample to Borsuk's conjecture, Bull. Amer. math. Soc. 29(1993), 60-62
	G. Kalai, Linear Programming, the simplex algorithm and simple polytopes, Math. Prog. (Ser. B) 79(1997), 217-234.