funded by the EPSRC project "New Techniques for Resolving Boundary Problems
in Total Search".
The project is led by John Fearnley (https://cgi.csc.liv.ac.uk/~john/) and
Rahul Savani (http://www.csc.liv.ac.uk/~rahul) and the position will run
for two years starting from the 1st of January 2024.
The project explores 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 particularly focuses 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
john.fearnley@liverpool.ac.uk.
The application form can be found here: https://bit.ly/064806
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* 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.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
