Ph.D. and PostDoc positions in Algorithms at IDSIA, USI-SUPSI, Lugano, Switzerland

 

The Algorithms and Complexity Group of IDSIA, USI-SUPSI, Lugano (Switzerland), opens

       2 Ph.D. positions

       1 PostDoc position up to 4 years.

These positions are supported by the Swiss National Science Foundation project "Ideal Membership Problems and the Bit Complexity of Sum of Squares Proofs", project n. no 200021_207429 / 1. November 2022-October 2026.

 

THE PROJECT

 

The project is on the interface of three very active areas of research in theoretical computer science and mathematics.

1.     The first one deals with polynomial ideals and their properties and goes all the way back to David Hilbert.

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

3.     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 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 a whole range of new very interesting problems.

 

References (chronological order):

1.     Monaldo Mastrolilli: The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain. ACM Trans. Algorithms 17(4): 32:1-32:29 (2021). Preliminary version appeared in SODA 2019.

2.     Arpitha P. Bharathi, Monaldo Mastrolilli: Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain. MFCS 2020: 13:1-13:13. Accepted by SIAM Journal on Discrete Math., 2022.

3.     Arpitha P. Bharathi, Monaldo Mastrolilli: Ideal Membership Problem for Boolean Minority and Dual Discriminator. MFCS 2021: 16:1-16:20.

4.     Andrei A. Bulatov, Akbar Rafiey: On the Complexity of CSP-based Ideal Membership Problems. To appear in STOC 2022: 54th Annual ACM Symposium on Theory of Computing.

5.     Andrei A. Bulatov, Akbar Rafiey: The Ideal Membership Problem and Abelian Groups. STACS 2022: 18:1-18:16.

 

OPEN POSITIONS

 

       The 2 Ph.D. positions are for 2+2 years (4 years is expected), 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).

       1 Postdoc position up to 4 years. The gross salary is around 80.000 CHF per year, with low taxes. There are no teaching duties and there is travel support. Candidates with strong background in mathematics or theoretical computer science will be considered. Candidates should hold (or be close to obtaining) a Ph.D. in Computer Science or related areas and should have a solid publication record. Background in approximation algorithms, universal algebra, semidefinite programming, algebraic geometry would be useful. There is no specific deadline; the position will be filled as soon as an eligible candidate with an appropriate background apply.

HOW TO APPLY

 

PostDoc applications can be sent at any time during the first 3 years of the project.

 

Ph.D. applications: applicants should submit the following documents (written in English)

to Prof. Monaldo Mastrolilli (monaldo at idsia.ch)

       Curriculum vitae with publications list (if any) and possibly link to the thesis.

       List of exams and their grades obtained during the Bachelor and the Master of Science.

       List of two/three references (with e-mail addresses).

       Motivation letter, including a brief description of past research experience and future interests (1-2 pages).

 

PostDoc applications: applicants should submit the following documents (written in English)

to Prof. Monaldo Mastrolilli (monaldo at idsia.ch).

       Curriculum vitae with publications list and possibly link to the thesis.

       List of two/three references (with e-mail addresses).

       Motivation letter, including a brief description of past research experience and future interests (1-2 pages).

 

Applications that are incomplete, submitted to other addresses, or submitted beyond the deadline, will be not accepted.

 

IDSIA

 

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.

 

CONTACT:

 

For any question, do not hesitate to contact:

Prof. Monaldo Mastrolilli

monaldo at idsia.ch

http://people.idsia.ch/~monaldo/