PhD position in algebraic algorithms in games and optimization

A PhD position is available in the joint INRIA, CNRS, and Sorbonne
Université (LIP6) team PolSys (https://polsys.lip6.fr/) in Paris. The
position is funded by the ANR JCJC program
GALOP (Games through the lens of ALgebra and OPtimization).


Scientific context:

Semidefinite programming (SDP) extends linear programming and has
become a fundamental ingredient in polynomial and combinatorial
optimization, complexity theory, game theory, quantum computing,
control, signal processing, and computational finance. The standard
tool to solve SDP problems is interior point methods. One of the
current challenges is to exploit the underlying algebraic formulation
to cope with the reliability issues of SDP and deduce more efficient
algorithms. For such a task, we should exploit the algebraic and
geometric structure of the polynomial systems that correspond to the
optimization problem. With these algebraic and optimization tools, we
can study the complexity of special classes of (continuous) stochastic
games and obtain precise bounds.

We invite applications for a full-time PhD position for three years at
the intersection of algebraic algorithms, optimization, and
theoretical computer science, with a view towards applications in game
theory.

A successful PhD candidate will work on one, or on a combination, of
the following topics:
- Deduce efficient algorithms and precise complexity and degree bounds
for important classes of stochastic games based on algebraic
formulations.
- Exploit the algebraic formulation of SDP to deal with
reliability issues.
- Exploit the structure of polynomial systems, for example
multi-homogeneity, sparsity, symmetry, properties of determinantal
varieties, to introduce improved algorithms for Groebner basis
and/or solving.
- Provide an efficient and certified open-source software for real
solving univariate polynomials and polynomial systems.


Profile:

- MSc in computer science or (applied) mathematics.
- Strong background in algorithms, knowledge of complexity theory.
- Skills in a programming language like C or C++ is a definitely plus.
- High command of written and oral language.
- Ability to work in a team.


Application:

The application should include:
- Letter of interest.
- Scientific CV.
- Contact information of two references (Title, Name, organization, e-mail).

The starting date of the PhD is expected to be early 2019 or soon after.


Potential candidates should send their application or questions
by the end of December 2018 to Elias Tsigaridas (elias.tsigaridas@inria.fr).