Event Details

Let us say that a nonlinear convex program is rational if it has a rational solution that can be written in polynomially many bits, if all its parameters are set to rational numbers. This class turns out to be surprisingly rich -- it captures solutions to several important problems in game theory and mathematical economics. In these two talks, we will show how the primal-dual paradigm was extended from its usual setting of PL-duality theory to obtaining combinatorial algorithms for solving rational convex programs.