## Thèses

#### Context

**IRIF** (CNRS and Université Paris Cité), Paris, France, is seeking excellent candidates for Ph.D. fellowships in all areas of Foundations of Computer Science. **Every year, about 20 new Ph.D. students** start their doctoral studies at IRIF.

IRIF (Institute for Research in Foundations of Computer Science) is a joint laboratory of the **CNRS** (French National Center for Scientific Research) and **Université Paris Cité**. Currently, it hosts about 90 permanent faculty members, 40 non-permanent full-time researchers, and 50 Ph.D. students.

The research conducted at IRIF is based on the study and understanding of the foundations of all areas of computer science. Such research work relies on mathematical concepts developed and studied within it, but it also contributes directly to mathematics. Typical areas include but are not limited to: algorithms, their design and analysis, automata theory and applications, combinatorics, complex systems, complexity, computational formalisms, distributed computation, foundations of programming languages, interactive proof assistants, graph theory and its algorithms, logic, networks, quantum computing, software development, systems modeling and verification. For further information about IRIF please see our presentation of IRIF.

#### Description of PhD studies at IRIF

In France, Ph.D. studies are typically **3 years** long and can be extended in some cases to **4 years**. Ph.D. fellowships are full-time research contracts with some optional additional activities such as teaching.
The **starting date** of the positions is usually in **October 1st**, but this may sometimes vary.
All IRIF Ph.D. students must register at Paris Doctoral School of Mathematical Sciences (ED386).

Many Ph.D. studies starting at IRIF are the continuation of master programs, such as the LMFI or the MPRI, but this is not mandatory and IRIF regularly welcomes Ph.D. students joining after a master in another French or foreign university.

IRIF also participates to two Graduate Schools of Université Paris Cité: Mathematical Sciences and Quantum Technologies.

Funding Ph.D. studies at IRIF can be obtained by applying to a scholarship through IRIF and its related partners (such as IRIF research grants, Université Paris Cité, regional programs, industrial partnerships …) or by applying to another institution independent from IRIF (such as his/her current institution, campus France, …).

In addition, Ph.D. students can be teaching assistants during their studies. More information (in french).

#### How to apply

It is advised to contact IRIF as soon as possible in order not to miss a possible call (see possible funding below).

Ideally, the **contact** should be the researcher you would like to work with. It can also be the head of the thematic group or head of the pole corresponding to your scientific interests (see the presentation of IRIF). Please avoid multiplying the contacts (alternatively, contact all concerned persons with a single e-mail so as they are aware of this).

Independently, there is also the possibility to directly apply to one or more **specific fellowships** funded by research grants. The list can be found below; it is not
exhaustive and might be updated at any moment.

In all cases, the candidate should **join a CV**, and is advised to give as much information as possible (such as **transcripts** of her/his marks for the bachelor and master program).

#### Possible fundings & topics

The Ph.D. fundings at IRIF are financed either by IRIF research grants, or by joint applications of IRIF members and the candidate to outside funding agencies with which IRIF is affiliated.

##### Generic fundings

There are several possibilities of fundings, and the candidate should contact IRIF for guidance.

IRIF depends on the **graduate school**
ED 386 - École doctorale de Sciences Mathématiques de Paris Centre. Several scholarships are allocated directly from that school every year. IRIF is also eligible to several funding programs from its partners, which allow the recipients to conduct doctoral research at IRIF among other possibilities.
Below are listed the most relevant programs for IRIF in 2022:

- ED 386 - École doctorale de Sciences Mathématiques de Paris Centre - Deadline June, 15th 2022, with an IRIF pre-submission deadline on May, 20th 2022.
- «Jean‐Pierre Aguilar» Fellowship of the Fondation CFM - (Local) Deadline June, 6th 2022
- A special program for applicants with disabilities is also available through with Doctorat Handicap - (Local) Deadline May, 2nd 2022

An application through Campus France is also possible for individual fellowships.

##### Specific topics

The following list describes potential Ph.D. topics at IRIF, some of them come with a dedicated scholarships.
Otherwise the candidate will have to apply with her/his potential advisor to one of the generic fundings.
This list is subject to be updated at any time.

*To add an opening, please contact direction@irif.fr.*

#### Beyond Worst-case complexity

In many situations, algorithms work on very specific data distribution. For example, social graphs follow a power law degree distribution and some very simple algorithms work well on these distributions. Which hard problems remain hard or become easy in this context? It is the main question asked for approximate algorithms, which include Property testing for decision problems, search problems, optimization and counting problems.

Funding: Apply to generic openings.
Contact : Michel de Rougemont

#### Fast algorithms for combinatorial optimization and machine learning

The goal of this project is to develop fast and practical solutions for fundamental algorithmic problems. This involves designing faster algorithms for classical problems in combinatorial optimization (involving graphs, matchings, submodular functions, matroids, etc.), and developing new theory relevant to modern machine learning (with a focus on deep learning).
The mathematical toolkit is based on modern techniques from continuous optimization, and interferes with other interesting theory from convex geometry, probability and numerical linear algebra.

Funding: Apply to generic openings. Contact: Adrian Vladu

#### Quantum computing

The Algorithms & Complexity group at IRIF (CNRS and Université Paris Cité), Paris, France, is offering multiple PhD positions to work on the theory of quantum computing. Special emphasis is on the development of quantum algorithms for optimization, machine learning, massive data, and cryptography. In case of interest, there will also be opportunities to collaborate with industrial partners.

Funding: Generic openings and internal grants. Contact Simon Apers.

#### Computational varieties

We aim to pursue the study of the Lambda Calculus through the lens of Universal Algebra, by dissecting the algebraic structure of lambda-theories.
Once suitable structure is found, new results in both fields are at hand,
as witnessed by recent work on n-dimensional Boolean algebras and clone algebras.

Funding: Apply to generic openings. Contact: Antonio Bucciarelli

#### Principles of programming languages for data science

In the last few years a new research is flourishing at the interface between the programming languages and the data science communities. The starting point is the understanding that core objects of data science such as complex neural networks, bayesian inference or optimization algorithms may in fact be expressed more synthetically and modularly by using higher-order and functional programming primitives. Our general goal is to develop and to apply to this new setting tools based on logic and lambda-calculus, such as type systems, semantics, logical relations, linear logic to improve the performance and certification of these objects.

Funding: Apply to generic openings. Contact : Michele Pagani.

#### Programming with proofs in classical realizability

Classical realizability is an avatar of the Curry-Howard correspondence between proofs and programs. It is the only one which allows to get programs from proofs in Zermelo-Fraenkel set theory. Despite some formal technicalities (it is closely related with Cohen's forcing) it gives fascinating informatic interpretation of theorems and axioms in ZF (for instance the axiom of dependent choice), in terms of operating systems, network and games. Recently, a program for the full axiom of choice was obtained.
The proposition of thesis could be to interpret the behaviour of some programs obtained in this way,
for instance from proofs of valid first order formulas. There are many other possibilities.

Funding: Apply to generic openings.
Contact : Jean-Louis Krivine