ERC Consolidator grant - FOREFRONT


Project Summary

The FOREFRONT project (Frontiers of Extended Formulations) investigates the modeling power of linear and semidefinite programming, in the context of combinatorial optimization. Within the emerging framework of extended formulations, it addresses the following question: Which problems can be modeled by a linear or semidefinite program, when the number of constraints and variables are limited?

We aim at answering this question as broadly as possible, without any extra assumption on the model used (such as, restricting to a particular hierarchy).

The project has strong geometric aspects because it seeks to quantify how efficiently we can describe or approximate a given polytope as the projection of a higher-dimensional polyhedron, or spectrahedron. It also has strong ties to (quantum) communication complexity, and approximation algorithms.

The theory of extended formulations offers a lot of exciting challenges, e.g., concerning linear programming approximate extended formulations, and (either exact or approximate) semidefinite programming extended formulations.

[Top]

Open Positions

The project has currently no open position. The project has currently 2 open Postdoc positions, both starting in Fall 2017. Both positions could be extended for a total of two years. Travel support is generous. For applying, please send me a CV and the names and email addresses of three references. E-mail enquiries about the position are welcome.

[Top]

This project is funded by the European Research Council under the EU's 7th Framework Programme (FP7/2007-2013). ERC grant agreement no. 615640.