Past lectures

Abstract

In these lectures we develop an emerging algorithmic theory of nonlinear discrete op- timization 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 sto- chastic systems; efficient randomized and approximative optimization of arbitrary nonlinear functions over combinatorial systems; and the universality theorem for rati- onal 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, unimo- dular matrices, Frobenius numbers, and polynomial identity testing and interpolation.

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

The lectures are accessible to anyone with standard undergraduate knowledge, in par- ticular linear algebra (though some exposure to basic complexity and linear program- ming may help intuition); the only main real requirement is mathematical maturity.

See http://ie.technion.ac.il/~onn/Nachdiplom/ for further information.