Mathematical Programming: Turing-completeness and applications to algorithmic analysis

Leo Liberti

Date and Time: 

Thursday, October 23, 2014 - 4:00pm

Event Location: 

Mohler Lab # 453

We provide a new proof of the fact that Mathematical Programming is Turing-complete, and show how it can be useful in the analysis of code, by presenting two applications. The first aims to find hard inputs for given programs. The second finds relaxations of the set of values taken by the program variables during execution, without actually executing the code.

Joint work with Fabrizio Marinelli, Universita Politecnica delle Marche.

Bio Sketch: 

Leo Liberti graduated in Mathematics from Imperial College London and the University of Turin, Italy, and received his Ph.D. in optimization from Imperial College. He was a postdoctoral fellow at Politecnico di Milano, then a professor at Ecole Polytechnique, France. He is now a researcher at the IBM "TJ Watson" research center in Yorktown Heights. He puts his efforts in helping to shape two communities: Mixed-Integer Nonlinear Programming and Distance Geometry.