Linear programming is the problem of maximizing a linear function φ subject to a system of linear inequalities. The solutions to these linear inequalities form a convex polyhedron P (called the feasible polyhedron") and Dantzig's simplex algorithm from the early 50s, can be described geometrically as moving from one vertex to an adjacent vertex of P.
In the lecture, I will overview some developments regarding linear programming and the simplex algorithms and present some outstanding problems.
Among these problems:
- Is there a strongly polynomial algorithm for linear programming?
- How large can the diameter of the graph of the feasible polytope of n inequalities with d variables be?
- Is there a pivot rule to the simplex algorithm that requires a polynomial number of steps?
- Does randomization "help" for pivot rules of the simplex algorithm?
- What is the computational complexity of the game Backgammon (שש-בש)?
The last question touches on several mysterious connections between linear programming and games.
Gil Kalai received his B. Sc. M.Sc. and Ph.D degrees in mathematics from the Hebrew University of Jerusalem. His Ph. D. Supervisor was Micha A. Perles. After a postdoctoral fellowship M. I. T, he returned as a faculty member to the Hebrew University and in 2016 he joined the Efi Arzi school of Computer Science at Reichman University. He was the recipient of the Pólya Prize in 1992, the Erdős Prize of the Israel Mathematical Society in 1993, the Fulkerson Prize in 1994, and the Rothschild Prize in 2012.
Kalai's main research areas are combinatorics, convexity and applications to theoretical computer science, mathematical programming, probability theory, quantum computing, and game theory. An influential 1988 paper by Kahn, Kalai and Linial on Boolean functions gave an early application of Fourier analysis in theoretical computer science, and subsequently Gil has applied Fourier methods to the study of random graphs, percolation, noise, and social choice. In 1993, Kalai and Kahn found a geometric object in 1325 dimensions that disproved the famous Borsuk Conjecture of 1933. Since 2005 he has studied noisy quantum computation. Kalai's writes a blog "Combinatorics and More" http://gilkalai.wordpress.com/.