## Thèses

#### Context

**IRIF** (CNRS and Université de Paris), Paris, France, is seeking excellent candidates for Ph.D. fellowships in all areas of Foundations of Computer Science. **Every year, about 15-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é de Paris**. 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.

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.

Funding Ph.D. studies at IRIF can be obtained by applying to a scholarship through IRIF and its related partners (such as Paris Doctoral School of Mathematical Sciences (ED 386), IRIF research grants, Université de Paris, 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 (the call opens in spring and its usual deadline is around mid-May).

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:

- The MathInParis Doctoral program will grant 20 PhD projects for international students to start a PhD program in September-October 2021. Application deadline: February, 13th 2021.
- The Paris Region PhD2 program will grant 30 PhD projects to start a PhD program in October 2021-January 2022 on Digital Sciences with an industrial partner. Application deadline: March, 2nd 2021.
- The DIM MathInnov Doctoral program will grant about 9 PhD projects in 2021. Application deadline: May, 20th 2020.
- The DIM RFSI (Computer science) will co-fund some PhD projects in 2021. Application must be done by the potential advisor. Application deadline: Spring 2021.

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

#### Property testing, quantum computing and their connection

In the age of “big data”, it is often impossible to process the huge amounts of data efficiently. Furthermore, the data may change dynamically, thus we need to get some results quickly, so that they correspond to a recent state. The main goal of the thesis is to examine two possible solutions for this problem: property testing and quantum computing, while also paying attention to some topics related to both.

Funding: Apply to generic fundings. Contact: Frédéric Magniez

#### Mock theta functions for root systems

Ramanujan's mock theta functions are certain combinatorial generating functions which resemble modular forms in several ways. They were first described by Ramanujan 100 years ago in his last letter to Hardy. Their “near modular” behavior was poorly understand for many years, but it is now known that it comes from the fact that the mock theta functions are holomorphic parts of harmonic Maass forms. This understanding follows in two steps – first, analytic techniques are used to rewrite the generating functions as number theoretic functions like Appell-Lerch series or indefinite theta functions, and from there the modular transformations can be studied. The analytic techniques involve the theory of basic hypergeometric series and Bailey pairs. This can be generalized to multivariable basic hypergeometric series for root systems, leading us to suspect that each of Ramanujan's mock theta functions is a special case of an interesting family of functions. The goal of this project is to use the generalized theory of Bailey pairs to detect these functions and express them as number-theoretic objects, and then to study their combinatorics and determine any modular transformation properties.

Funding: Apply to generic openings.
Contact: Jeremy Lovejoy

#### 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

#### 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

#### Coloring and packing problems on signed graphs

A signed graph is a graph where edges are assigned signs: positive and negative.
A switching of a signed graph is to multiply signs of all edges of an edge-cut to “-”.
Extending notions of graphs, signed graphs equipped with switching, provide a framework in which one can strengthen results, extend ideas, fill in the gaps in theories and, sometimes, prove results that are not possible in plain graph theory. Specific projects to be considered in this direction are: 1. Various chromatic numbers of signed graphs, 2. Several packing problems, 3. Flow problems.

Funding: Apply to generic openings. Contact: Reza Naserasr

#### Quantum algorithms for machine learning and optimization

Funding: Apply to generic openings. Contact: Iordanis Kerenidis

#### 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

#### Revisiting the connexion between lambda-calculus and linear-logic

This thesis proposal is about Proof Theory and its connection with Computer Science in the framework of the Curry-Howard correspondence. One main objective will be to revisit the classical result of confluence in Multiplicative-Exponential Linear Logic, the fragment of linear logic that allows to represent the full lambda-calculus, in order to produce a new solution based on a definition of simultaneous reduction of parallel cuts recently introduced by Chouquet and Vaux-Auclair. A second direction of work will be the study of the !-calculus, introduced by Ehrhard and Guerrieri as an extension of the lambda-calculation inspired by linear logic proof-nets, implementing a so-called call-by-push-value decomposition of beta-reduction. We will develop a criterion for capturing the image of this calculus within proof-nets, similar to the Danos-Regnier criterion for the lambda-calculus. This well lead to a more uniform and principled understanding of the implementation of the various reduction strategies of the lambda-calculus within Linear Logic (call-by-name, call-by-value, call-by-need) and to a common framework for the design of static tools for analyzing the resource consumption of programs based on Linear Logic and its denotational models.

Funding: Apply to generic openings. Contact: Thomas Ehrhard

#### Distributed Computing with Mobile Agents

The objective of the thesis is to provide distributed mobile computing with abstractions enabling the development of generic techniques susceptible to be applied to large classes of distributed
computing models, despite their potential differences. Algebraic topology is of course one tempting approach. However, the mode of interactions between mobile agents is rather more complex and richer than the ones between static processes in systems, and thus, even though preliminary work exist in this direction, using algebraic topology for modeling the entire domain of distributed mobile computing is probably challenging, and not in reach within a medium term perspective.

Funding: Apply to generic openings. Contact: Pierre Fraigniaud

#### Graph modular decomposition as a means of compression

As part of the ANR Coregraphie project, a PhD thesis is proposed at IRIF on the modular decomposition of graphs with a view to their compression. It will start in September 2021 and will be supervised by Fabien de Montgolfier and Stefano Zacchiroli. More details.

Funding: ANR Coregraphie project. Contact: Fabien de Montgolfier

#### Operator methods for quantitative analysis of timed and stochastic systems

In the context of cyber-physical systems (such as automotive control), we
typically want to answer quantitative questions such as “how safe?”, “how
robust?”, “how fast?”, “how costly?” rather than just answer to binary
questions (“Is it safe?”, and so on).

Such systems are typically described by timed and/or stochastic models (timed
automata, Markov decision processes, … ), where many verification techniques
are based on the study of the properties of an, often implicit, transfer
operator.

The goal of this thesis is, in this setting, to explore common patterns based
on the study of transfer operators, to write algorithms for quantitative
verification of timed and/or stochastic systems and to promote them within the
different tasks of project MAVeriQ.

Full text.

Funding: ANR Project MAVeriQ. Contact: Aldric Degorre