|
Main
Page
Graduate
Program
Undergraduate
Program
Course Information
Course
Web Pages
Our
Research
Research
Areas
Technical
Reports
Faculty
Graduate
Students
Research
and Technical Staff
Administrative
Staff
Alumni
Degree
Recipients
Calendars
Computing
Facilities
CS
Talks Mailing List
Yale
Computer Science FAQ
Yale Workstation Support
Computing
Lab
AfterCollege
Job Resource
Graduate
Writing Center
Contact
Us
History
Life in the Department
Life About Town
Directions
Faculty
Positions
City
of New Haven
Yale
Applied Mathematics
Yale
C2: Creative Consilience of

Computing and the Arts
Yale
Faculty of Engineering
Yale
GSAS Staff Directory
Yale
University Home Page
Google Search
Yale Info Phonebook
Internal |
|
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. |

|
 |