and Technical Staff
Computer Science FAQ
Yale Workstation Support
Life in the Department
Life About Town
of New Haven
C2: Creative Consilience of
Computing and the Arts
Faculty of Engineering
GSAS Staff Directory
University Home Page
Adjunct Professor of Computer Science & Mathematics
Office Location: AKW 404
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
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
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
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.
G. Kalai, Linear Programming,
the simplex algorithm and simple polytopes, Math. Prog. (Ser. B)