Tuesday, October 18, 2022

[DMANET] Postdoc in Computational Complexity in Lisbon

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-bounds (of any kind). Papers on CCC, but
also STOC/FOCS/SODA/ICALP/RANDOM/STACS/MFCS/CSR (track A) are a sign you
are likely a good fit for the project.

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
* 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). Gross salary is 45.000-49.000
EUR/year (depending on experience), which, if I computed correctly, should
amount to ca. 2300-2500/month net salary.

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 wish to apply, please send me your CV, a short cover letter, and two

If you have any questions, feel free to contact me: bruno.loff@gmail.com.

See you,
Bruno Loff

* 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.
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/