Faites connaître cette offre !
Reference : UMR8243-EVARYC-015
Workplace : PARIS 13
Date of publication : Friday, May 22, 2020
Scientific Responsible name : Claire Mathieu
Type of Contract : PhD Student contract / Thesis offer
Contract Period : 36 months
Start date of the thesis : 1 September 2020
Proportion of work : Full time
Remuneration : 2 135,00 € gross monthly
Description of the thesis topic
The proposed subject is part of a research project that is aimed at laying down sounder theoretical foundations for algorithms that do not operate in the traditional three-phase static setting of input-computation-output, but rather are suited for modern applications where the input is not fully readily available at once before computation starts, e.g., is massive, scattered or disorganized, plagued with errors, or constantly evolving. Such algorithms must utilize techniques from various algorithmic domains such as streaming algorithms (for data arriving as a stream), online algorithms (for output computed on the fly as data is read), algorithms for noisy data, or distributed algorithms. In terms of problems, the nature of combinatorial optimization problems can change dramatically in such fluid environments.
For example, what happens to stable marriages when preferences evolve? One may wish, e.g., to set up a stochastic or incremental model for the evolution of preferences, and then examine the effect on the stability of matchings and the efficiency of updates.
In another direction, one may wish to study models of graphs evolving over time, or dynamic networks, whether it be in the context of human social networks, communication networks, or biological systems. For example in social networks, one may wish to study the robustness and efficiency of algorithms for classic graph problems such as shortest paths. Or in the context of collective animal behavior, like flocks of birds or school of fish, one may wish to study, sometimes in the presence of game theoretical effects, shortest paths or other problems related to food foraging.
In yet another direction, one may study classic rank aggregation problems when voters and candidates change over time, or study the robustness of algorithms when the data is noisy. In the same vein, one may analyze the dynamics of school preferences over the years when a school's reputation in a given year depends on previous students' choices, and the possibility of the spontaneous emergence of a strict ranking between schools as a consequence of purely random initial features.
The selected Ph.D. student will work on both developing algorithms as well as on proving lower bounds, most notably unconditional lower bounds based on information theory techniques or communication complexity. The exact topic, as well as the specific thesis advisor, will be decided upon discussions with the successful candidate. The topic of this research work falls under the research areas of the joint French-Israeli Laboratory on Foundations of Computer Science (FILOFOCS) (joint to the CNRS, Univertsité de Paris, Tel-Aviv University, The Weizmann Institute of Science, The Hebrew University of Jerusalem).
The Research Institute on the Foundations of Computer Science (IRIF) is a research unit co-founded by CNRS and Université de Paris, as UMR 8243. It results from the merging of the two research units LIAFA and PPS on January 1st, 2016. IRIF hosts two Inria project-teams.
The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences.
The topic of this research work falls under the research areas of the joint French-Israeli Laboratory on Foundations of Computer Science (FILOFOCS) (joint to the CNRS, Univertsité de Paris, Tel-Aviv University, The Weizmann Institute of Science, The Hebrew University of Jerusalem), and if desired by the student, the Ph.D. research may include a stay or stays at the Israeli partner institutions.
Constraints and risks
If desired by the student, the Ph.D. research may include a stay or stays at the Israeli partner institutions.
The PhD contract has to begin between september and november 2020.
We talk about it on Twitter!