Abstract. In these lectures we develop an emerging algorithmic theory of nonlinear discrete optimization based on exciting recent advances over the last few years, extending the well-established theory of linear discrete optimization.

We will cover some of the highlights of this theory including efficient algorithms for maximization of convex functions over sets of integer points presented by inequalities or oracles; maximization and minimization of convex functions over integer n-fold systems and integer stochastic systems; efficient randomized and approximative optimization of arbitrary nonlinear functions over combinatorial systems; and the universality theorem for rational polytopes and their integer points.

We use a variety of geometric and algebraic methods, some classical and some very recent, that will be developed as part of the lectures, such as the theory of Graver bases and their stabilization over n-fold systems and stochastic systems, zonotopes, unimodular matrices, Frobenius numbers, and polynomial identity testing and interpolation.

We will also discuss some of the many applications of this theory in statistics, operations research, and commutative algebra, including privacy in statistical databases and experimental design; nonlinear transportation and multicommodity flows; error-correcting codes and construction of universal Grobner bases on the Hilbert scheme.

The lectures are accessible to anyone with standard undergraduate knowledge, in particular linear algebra (though some exposure to basic complexity and linear programming may help intuition); the only main real requirement is mathematical maturity. See http://ie.technion.ac.il/~onn/Nachdiplom/ for further information.

Time:       Wednesday 1:15 - 3:00 p.m.
Auditorium:        HG G 43 (HWZ)
Begins:   March 4
 

M. Struwe