Wednesday, March 23, 2022

[DMANET] Three-year Postdoc Position in Algorithms and Complexity

We are seeking candidates for a three-year postdoctoral research position
funded by the EPSRC project "New Techniques for Resolving Boundary Problems
in Total Search"

The project will be led by John Fearnley (
and Rahul Savani ( and will run for three
years starting from the 1st of September 2022.

The project will explore new techniques for showing hardness in TFNP,
following on from the STOC 2021 best paper "The complexity of gradient
descent: CLS = PPAD ∩ PLS". The project will particularly focus on the
complexity class CLS, which contains problems from a wide variety of
disciplines, including:
* Algorithmic Game Theory (eg. Network congestion games, Network
coordination games, Shapley stochastic games)
* Formal Verification (eg. Tarski fixed points, Contraction map fixed
points, Unique sink orientations, Simple-stochastic games)
* Optimization and Machine Learning (eg. finding KKT points of
polynomials, gradient descent in a neural network)

An ideal candidate will have a strong research background in at least one
of the three areas listed above. That candidate will also have, or be close
to completing, a PhD in Computer Science or a related area.

Informal enquiries are welcome, and should be directed to

The application form can be found here:

* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.