AIRO Young Opportunity

30 Jun 2022
Algorithms and Complexity Group of IDSIA, USI-SUPSI
The Algorithms and Complexity Group of IDSIA, USI-SUPSI, Lugano (Switzerland), opens 2 Ph.D. positions and some PostDoc positions. These positions are supported by the Swiss National Science Foundation project "Ideal Membership Problems and the Bit Complexity of Sum of Squares Proofs" (November 2022-October 2026).

The project is on the interface of three very active areas of research in theoretical computer science and mathematics. The first one deals with polynomial ideals and their properties and goes all the way back to David Hilbert. The second one is a widely used tool in complexity, algebraic and semi-algebraic proof systems such as Sum-of-Squares (SoS), where the main question is when a proof of a certain property of a polynomial can be efficiently found. The third area is the analysis of the complexity of constraint satisfaction problems (CSPs), mainly through the universal-algebraic approach. These areas address key problems in theoretical computer science, they produce a very significant amount of world class research, with many publications in world-leading venues in theoretical computer science. The proposed project is about a new direction of research combining these three areas mentioned above. This new direction of research was recently initiated by the PI of this project in a series of publications and followed up by other works by world-leading experts on universal-algebraic methods in CSPs. The new direction proposes to combine two widely used methodologies in a new way, with an algebraic geometry view used to bring them together. This new combination opens up a whole range of new very interesting problems.

The Ph.D. positions are for 2+2 years, and they are supposed to start on November 1st 2022 with moderate flexibility. The gross salary is around 50.000 CHF per year, with low taxes. The position involves a moderate teaching load (as teaching assistant) at USI. There is travel support. Candidates should hold (or be close to obtaining) a Master Degree in Computer Science or related areas. A solid background in Algorithms, Computational Complexity, Discrete Mathematics, Mathematical Programming is helpful. A good knowledge of written and spoken English is also required (while knowledge of Italian is not needed).

The PostDoc positions are initially for 1 year, but an extension by 1 extra year is expected (further extensions are possible). The project supports 1 PostDoc position per year on average. The gross salary is around 80.000 CHF per year, with low taxes. There are no teaching duties and there is travel support. Candidates should hold (or be close to obtaining) a Ph.D. in Computer Science or related areas and should have a solid publication record and a solid background in at least one of the areas mentioned above.

IDSIA offers an international working environment. Lugano is a tidy and lively town, with a wonderful view on Ceresio lake and mountains around. Ticino Canton offers many opportunities for hiking, biking, skiing, etc. Local restaurants serve very good food.

The interested candidates should email a detailed CV and contact details of 2-3 references to Prof. Monaldo Mastrolilli, monaldo at
For full consideration, Ph.D. and Postdoc applications should be sent within 30th June 2022. Further PostDoc applications can be sent at any time during the first 3 years of the project.

For any question, do not hesitate to contact:
Prof. Monaldo Mastrolilli
monaldo at