Wednesday, September 21, 2022

[DMANET] Postdoctoral Fellowships in Computational Complexity

Dear all,

I'm looking for two or three postdoctoral researchers to join me at the
University of Lisbon, as part of the ERC Starting Grant "The Hardness of
Finding Good Algorithms".

The project focuses on metacomplexity and unconditional lower-bounds. We
will study problems around formula complexity, circuit complexity,
communication complexity, data structures, etc, both classical and quantum
(but with more emphasis on classical).

I'm looking for strong candidates with a background in maths and
theoretical computer science, and I'm particularly interested in people who
have proven unconditional lower-bound (of any kind). The following topics
currently appear to be relevant to different parts of the project, so if
you are knowledgeable of and/or interested in learning about some of them,
all the better:
* communication complexity
* representation theory of finite groups
* convex optimization,
* interior-point methods (including implementations)
* stochastic games
* data-structure lower-bounds
* algebraic complexity

The starting date is flexible, between March-September 2023. The position
is for 2 years, with the possibility of extension until March 2028. There
is generous travel support available and no teaching duties (but frequent
contributions to our seminar are expected). Salary is circa 50k EUR/year
gross. That amounts to ca. 2800 EUR/month net salary (this includes holiday
subsidies, so it's 2400/month + 2400 two times per year).

I expect two of the positions to be filled by mid-late January 2023, at the
latest. A decision on individual applicants will not be made before
November 1, so you may think of that as a soft deadline for applying. After
November 1, someone may have filled the position already, but there is
flexibility in the number of positions, so you may apply anyway.

You may see a longer description of the project at:

If you have any questions, feel free to contact me:

See you,
Bruno Loff

* 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.