The Hardness of Finding Good Algorithms (HoFGA)

We are hiring!

We are currently looking to hire 2-3 postdocs to begin in March-October 2023. 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 (compared with cost of living, you can expect a very high quality of life).

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

If this piques your interest, send me an email:

The project

We are broadly interested in answering the following question:

Fix some computational model. Now suppose we are given a full description of a computational problem, and wish to find an efficient algorithm for solving it, or at least to estimate its computational complexity, in the said model… How hard is this algorithm-finding/complexity-estimation task?

We are interested in answering this question for different computational models, and especially interested in understanding when is the above task NP-hard?

We wish to study this question for decision trees, communication protocols, Boolean circuits and formulae, data structure problems, algebraic models, streaming models, various combinatorial complexity measures of complexity such as certificate complexity, partition number, etc, etc.

We will also work in various follow-up questions that arose when thinking about these things. And, more broadly, we are interested in proving unconditional lower-bounds of any kind, and especially in understanding the computational complexity (the “naturalness”) of the hardness-implying properties used in such proofs.