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
·
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", project n. no 200021_207429 / 1.
November 2022-October 2026.
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.
·
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).
·
The PostDoc
positions are initially for 1 year, but an extension by 1 extra year is
expected (further extensions are possible in exceptional cases). 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.
For full consideration, Ph.D. and Postdoc applications
should be sent within the 3rd July 2022.
Further 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) and through the appropriate form.
·
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) and through the appropriate form.
·
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 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.
For any question, do not hesitate to contact:
Prof.
Monaldo Mastrolilli
monaldo at idsia.ch