Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Initiation to Research

Person in charge: Ph. Schnoebelen

The course starts Tuesday Sept. 14th, 2021 in room 1Z53.

Organization:

Sept. 14th, 2PM (room 1Z53): Introduction to the course & description of available workshops.

Sept. 17th, 9AM: Deadline for submitting your preferences (see below).

Sept. 17th, 2PM: Assignment of students to groups announced.

Sept. 21st, 2PM: Start of first-session working groups (short and long).

Nov. 16th, 2PM: Start of second-session short working groups (while long working groups continue).

General Presentation

The “Initiation to Research” course (3 ECTS) embeds you in a working group (called “workshop”) tackling some research problem under the guidance of a senior superviser. The group meets once a week in order to assess progress, fix/update its short and long-term goals, assign tasks to participants. Research work is done between these meetings, working either alone or in some subgroup. Between the weekly meetings, communication with the group is often necessary and use ad-hoc means from email to impromtu discussions.

The pedagogical objectives of these workshops is to develop some specific skills by practicing them in a resarch-oriented setting. These skills are (list not exhaustive):

- Assessing the state of the art on some question/problem: specifying the scope of the question, assessing what are the main questions and why they are important or difficult or .., round up the relevant litterature, organize the existing contributions historically.

- Formulating a problem formally: choosing definitions, stating hypotheses to be proven/disproven, identifying subproblems or special cases, finalize proven results by either expanding/generalizing them or proving impossibility of extensions, find connections with problems in other contexts.

- Presenting/explaining a research result to your colleagues: highlighting what is easy and what is tricky, what is original and what is standard. Also, explaining what remains unclear and why.

- Understanding why a research problem is important: Identifying the underlying stakes, the implicit motivations, the potential applications, the future perspectives.

- Understanding the rules of research as a profession/career: how to write a curriculum vitae, how to find a position, where to publish a research paper and how to write it, what is plagiarism really, where and how to get funding for one's research, etc.

Description: Students will be enrolled in either one long workshop spanning the whole semester, or two short workshops over the two halves of the semester. Joining a long workshop allows investigating a research topic in more depth. Joining two short workshops allows for more diversity in research topics, style of supervision, sets of colleagues with whom to collaborate.

Planning: Each workshop has a scheduled group meeting on Tuesday afternoons during the semester (half semester for short workshops). Other interactions outside this time slot can be organized on a call-by-need basis, as the superviser deems necessary.

Language: Workshops will be in English (unless everyone prefers French or another language).

Evaluation: Each workshop has its own guidelines/rules/.. for evaluation (see details below).

Long workshop(s), from Sept. 21st, 2021 to Jan. 11th, 2022

WG L1 “Ordinals” / G. Dowek

Superviser: Gilles Dowek.

Room: MO07 (Mezzanine level)

Participants: Cyril Pujol, Thomas Lamiaux, Marius Belly–Le Guilloux, Rémi Pallen, Quentin Chuet, Neha Rino, Pranay Agrawal, Adam Allombert-Goget.

Keywords: Termination; consistency; provability.

Description: Termination is the most practical problem in computer science as many bugs manifest as a program never returning. It also plays an important part in the relation between computer science and logic as the first problem proved undecidable was the halting problem.

This workshop will focus on a universal method to prove termination of programs: the use of ordinals.

We shall in particular attempt to build programs that terminate but whose termination cannot be proved in arithmetic.

Expected workload: about four hours per week outside of the classroom.

Schedule: weekly meeting every Tuesday 14h-16h, starting Sept. 21st, 2021.

Grading: Will be done by assessing the quality of participation in class discussions, the contributed teamwork, scientific rigor, pedagogical skills.

Short workshop(s) for first session, starting Sept. 21st, 2021

WG SA1 “Distributed synthetic microbiology” / M. Függer

Superviser: Matthias Függer.

Room: 1J07

Participants: Robin Sobczyk, Paul Robert, Gabriel Jeantet, Thomas Michel, Quentin Sinh, Neven Villani, Sunheang Ty.

Keywords: Distributed systems; Microbiology; Synthetic biology; Circuit design; Dynamic networks.

Description: The course is organized as a short research project. It starts with a brief introduction into synthetic microbiological systems - with a focus on bacteria. We will then study such systems from a circuit design and distributed computing point of view in small groups.

Previous knowledge in microbiology, circuit design, or distributed computing is not obligatory.

Methods used will be from mathematical analysis, simulations, algorithm and circuit design - with the focus depending on the group's interests.

Pedagogical objectives: The objective is to learn to work within a scientific team. The team will choose a currently open research question, investigate the state-of-the-art and try to tackle the question.

Work includes: organization of research meetings on existing work, creative work on new ideas, and writing them down in a short research paper.

Expected workload: Approximately 5h/week (2h/week in class). Be aware that work besides in-class-time is expected (on average 2-3h/week)

Todo from your side:

  • Don't forget to write me a subscribe mail for the course at latest after the first meeting.

Planning: Team meetings are announced here. Check this page regularly for updates. Updates will also be sent via mail, once you are subscribed. Typically meetings are on Tuesday 14.00-16.00.

  • Sept. 21, 14.00-16.00: NOTE: This course starts on Sept. 28. There is no lecture on 21st.
  • Sept. 28, 14.00-16.00: Organization and Preliminaries
    • Initial presentation of research area
    • Todo until next time:
      • Write me a subscribe mail
  • Oct. 05, 14.00-16.00: Discussion of research questions in class. Forming groups.
  • Oct. 12, 14.00-16.00: Presentation and discussion of current research state in class. Timeline for next 3 weeks.
  • Oct. 19, 14.00-16.00: Presentation and discussion of current research state in class.
  • Oct. 26, 14.00-16.00: tba
  • Nov. 02, 14.00-16.00: tba
  • Nov. 09, 14.00-16.00, group-wise, tba

Literature (more to come)

  • If you cannot access a paper let me know.
  • From class (lac operon)
    • Díaz-Hernández and Santillán “Bistable behavior of the lac operon in E. coli when induced with a mixture of lactose and TMG”, Frontiers in Physiology, 2010
  • Components & tutorials on design:
  • Single cell:
    • Brophy and Voigt “Principles of Genetic Circuit Design”, Nature Methods, 2014
    • Nielsen et al. “Genetic circuit design automation” Science, 2016
    • Siuti et al. “Synthetic circuits integrating logic and memory in living cells”, Nature Biotechnology, 2013
    • Guiziou et al. “Hierarchical composition of reliable recombinase logic devices”, Nature Communications, 2019
  • Robustness:
  • Debugging/Characterization:
    • Gorochowski et al. “Genetic circuit characterization and debugging using RNA‐seq”, Mol Syst Biol., 2017
    • Borujeni et al. “Genetic circuit characterization by inferring RNA polymerase movement and ribosome usage”, Nature Communications, 2020. https://doi.org/10.1038/s41467-020-18630-2
  • Homologous recombination
    • Fujitani et al. “Dependence of Frequency of Homologous Recombination on the Homology Length”, Genetics, 1995.
  • Distributed:
  • Liao et al. “Rock-paper-scissors: Engineered population dynamics increase genetic stability”, Science, 2019
  • Omar Din et al. “Synchronized cycles of bacterial lysis for in vivo delivery”, Nature, 2017 & Chowdhury et al. “Programmable bacteria induce durable tumor regression and systemic antitumor immunity”, Nature Medicine, 2019
  • Regot et al. “Distributed biological computation with multicellular engineered networks”, Nature, 2011
  • Sardanyés et al. “Computational implementation of a tunable multicellular memory circuit for engineered eukaryotic consortia”, Frontiers in physiology, 2015
  • Cummings et al. “Probability 1 computation with chemical reaction networks”, International Workshop on DNA-Based Computers, 2014
  • Esvelt et al. “A system for the continuous directed evolution of biomolecules” Nature, 2011

Grading: Students will be evaluated based on their involvement during team meetings (50%), and final writeup (50%).

WG SA2 “Quantum networks theory” / P. Arrighi

Superviser: Pablo Arrighi

Room: 1K07

Participants: Emilien Lemaire, Paul Patault, Kathleen Barsse, Benjamin Loison, Arnaud Daby-Seesaram, Takek Tohme.

Keywords: Quantum computing; distributed computing; quantum superpositions of graphs.

Description: A fundamental question in Computer Science is simply : What is a computer? Can we come up with a mathematical definition that captures the fundamental resources that are granted to us by nature, namely both spatial parallelism and quantum parallelism? In this class, the students will be given access to a couple of recent papers claiming to achieve this goal. They will study them, try to find mistakes or unproven claims, and seek to complete the results of these papers, by taking on the perspectives mentioned in the conclusion.

Pedagogical objective: Learning the basics of quantum theory. Mastering the content of a complex paper. Suggesting improvements on the state of the art. Proving a Lemma. Establishing connections between models.

Expected workload: around 5 hours per week in addition to attending the sessions.

Planning: Tuesday, 14:00-16:00, starting Sept. 21st, 2021.

Grading: Ability to understand a paper and help others understand it (25%). Ability to suggest ideas for improvements (25%). Ability to prove a Lemma (25%). Oral participation (25%).

WG SA3 “Understanding a Research Topic / Practice of State of the Art and Bibliography” / Th. Chatain

Superviser: Thomas Chatain

Room: 1M07

Participants: Emma Caizergues, Baptiste Chevalier, Taïssir Marcé, Bastien Lhopitallier, Julien Veron, Nicolas Dumange.

Keywords: State of the art; Synthesis; Bibliography; Identification of new research problems.

Description: Every group of two students extracts, from a recent research article, the state of the art of the research topic, understands and explains the interest of the contribution in regard to the major works in the field. They also propose ideas for new research in the area.

The research topic will be chosen by the students and validated by the teacher.

Pedagogical objective: Practice of bibliography and state of the art, become familiar with the style and contents of introductions of scientific articles, understand the life of a scientific community (major conferences, topics of interest...)

Expected workload: around 5 hours per week in addition to attending the sessions.

Planning: every Tuesday, 14:00-16:00, starting Sept. 21st, 2021.

Grading: 1/4 bibliography; 1/4 synthesis of results and identification of research questions; 1/4 presentation; 1/4 write an introduction to an article.

WG SA4 “Generic Complexity” / H. Comon

Superviser: Hubert Comon.

Room: 1P82

Participants: Théo Rudkiewicz, Francis Durand, Antoine Grimod, Maroun Ayli, Lucas Froyssey, Hervé Sabrié, Léo Mangel.

Description: The usual definition of (Turing) computability (resp. complexity) is stated as: given a set of inputs I and a subset Q ⊆ I, is there a halting Turing machine (resp. a Turing machine running in time/space f(n)) that, on any d ∈ I, halts (resp. halts in time/space bounded by f(|d|)) with answer 1 when d ∈ Q and answer 0 otherwise.

Generic complexity, roughly, revisits this notion of computability (resp. complexity) as follows: given a distribution on a set of inputs I, is there a halting Turing machine (resp. a Turing machine running in time/space f(n)) such that, with probability 1, on d ∈ I, it halts (resp. halts in time/space bounded by f(|d|)) with answer 1 when d ∈ Q and answer 0 otherwise. In other words, we only ask that the machine gives the answer almost surely.

In this working group, we propose to investigate this notion. In particular, a question is its relevance.

Pedagogical objectives:

  • Working together, on a shared project.
  • Improve the communication
  • Improve the scientific workplan
  • Improve scientific papers reading
  • Marginaly, learn new notions

Organization: The group will meet every Tuesday at 2pm, starting Sept. 21st. We will start with two papers, each of which will be presented to the group by a team of students:

  • J. Hamkins & A. Miasnikov. “The halting problem is decidable on a set of asymptotic probability one”, 2006.
  • R. Gilman et al. “Report on generic case complexity”, 2007.

We will discuss together what should be investigated next in order to answer the question: when is generic complexity relevant ?

Short workshops for second session, starting Nov. 16th, 2021

WG SB1 “Algorithms for tropical algebra” / Ph. Schnoebelen

Superviser: Philippe Schnoebelen.

Room: 1J07

Participants: Théo Rudkiewicz, Paul Robert, Kathleen Barsse, Quentin Sinh, Francis Durand, Antoine Grimod, Lucas Froyssey.

Keywords: Tropical Algebra; Algorithms; Logic.

Description: Tropical algebra studies rings and semirings based on max,+,-∞,0 instead of +,*,0,1, see wikipedia for more details.

The starting problem for us is to compute efficiently values of the form Mnv for M a matrix and v a vector in tropical algebra. Can it be done in time polynomial in |M|+|v|+log n? In linear time?

This is the occasion to learn about tropical algebra as it appears in many fields of computer science: probabilistic systems, control theory, language theory, algorithms etc. We'll use the starting problem as motivation for reading papers, presenting fundamental results to the working group, identifying important research directions, etc.

The group will meet weekly and will use emails, chats, .. for exchanges between two meetings.

Pedagogical goals: The working group will be an opportunity for attacking a research problem while working as a group. We will experiment how tasks like gathering bibliography, understanding complex results, inventing new techniques, validating them, writing down proofs, checking the proofs, can be done collectively.

Expectations: It is expected that each participant will contribute his/her ideas, time & energy, ensuring group success. The group can be successful even if we do not produce a valid algorithm.

Workload: Approximately 5 hours per week (including the weekly meetings).

Planning: Six meetings on Tuesdays 14h-16h, starting Nov. 16th, 2021.

Grading: Each participant will receive a mark made of (50%) the superviser's assessment of his/her contributions to the common project, and (50%) the superviser's assessment of the quality of his/her oral presentations and written material.

WG SB2 “Compiler Correctness” / G. Melquiond

Superviser: Guillaume Melquiond.

Room: 1K07

Participants: Emilien Lemaire, Paul Patault, Bastien Lhopitallier, Sunheang Ty, Léo Mangel, Neven Villani.

Keywords: Semantics; Compilation; Formal proof.

Description: More often than not, a bug in an executed program was already present in the original source code. But it might also happen that the bug was introduced during compilation. This should not come as a surprise, since optimizing compilers are intricate pieces of code and thus likely to contain bugs themselves. One could even argue that it is futile to ensure that source code is bug-free, as the compiler might later mess with it. The correctness of compilers is thus of critical importance and formal methods have a role to play.

Pedagogical objectives: The focus of this workshop is not so much about research itself, but on all the associated activities: validating some research work, writing a scientific publication, evaluating and reviewing papers, presenting at a conference, and so on.

Prerequisites: As the workshop does not aim at making scientific breakthroughs, there is no specific prerequisite. Moreover, all the needed concepts will be explained during the first session. That said, it might help to have some general culture about semantics, compiler optimizations, and formal proofs.

Grading: One third for synthesizing a paper, one third for evaluating papers, and one third for presenting a result.

Bibliography: (to be completed as the group performs a survey of existing results):

  1. “VLISP: A verified implementation of Scheme”. Guttman, Ramsdell, Wand. LSC, 1995
  2. “Translation validation”. Pnueli, Siegel, Singerman. TACAS, 1998.
  3. “A formally verified compiler back-end”. Leroy. JAR, 2009.
  4. “CakeML: A verified implementation of ML”. Kumar, Myreen, Norrish, Owens. POPL, 2014.

WG SB3 “Approaching a cross-disciplinary topic” / L. Fribourg

Superviser: Laurent Fribourg

Room: 1M07

Participants: Baptiste Chevalier, Maroun Ayli, Takek Tohme, Julien Veron, Hervé Sabrié, Thomas Michel.

Description: The increasing complexity of research objects (energy network, living cell, autonomous vehicles, swarm of drones,...) imposes more and more the collaboration and interaction of theories from two (or even more) different disciplines. These interactions are particularly sensitive in computer science since this discipline is often found at the border of other disciplines, sometimes even leading to the creation of new disciplines (bioinformatics, quantum computing,...). The objective of this workshop is to prepare the student to understand and master the principles and conceptual tools of the other discipline which faces computer science at the frontier where both interact.

Pedagogical objectives:

The aim of the course is to:

  • identify an object of cross-disciplinary research, and a scientific frontier where computer science interacts with an external discipline (mechanics, dynamics, biology,...), and
  • characterise the traversing flows of information as well as the specific concepts according to which these flows are elaborated on both sides.

One way to start the working group will be to identify and analyse articles dealing with a given interdisciplinary subject. Examples include:

  1. Feynman, Richard P. (1986) : Quantum Mechanical Computers
  2. Shor Peter (1992) Scheme for reducing decoherence in quantum computer memory
  3. Shulman MJ, Steinberg CM, Westmoreland N (February 1981). “The coding function of nucleotide sequences can be discerned by statistical analysis”. Journal of Theoretical Biology. 88 (3): 409–20.
  4. Soinov, L. Bioinformatics and Pattern Recognition Come Together Journal of Pattern Recognition Research (JPRR), Vol 1 (1) 2006 p. 37–41

This experience will help the participants when, later in their career, they will have to present their chosen research area.

Schedule (tentative): Weekly meeting every Tuesday 14h-16h, starting Nov. 16th, 2021.

  • meeting 1 : the superviser presents the scientific context of the article.
  • meeting 2 : the article is presented by two participants working as a pair, and discussed by the group.
  • meetings 3-4-5 : some following paers are identified and presented by more pairs.
  • meeting 6 : a synthetic survey is written collectively.

Expected workload: a few hours weekly.

Grading: will reflect involvement and quality of contributions.

WG SB4 “Access Control and Security Policies” / H. Comon

Superviser: Hubert Comon.

Room: 1P82

Participants: Robin Sobczyk, Gabriel Jeantet, Benjamin Loison, Nicolas Dumange, Arnaud Daby-Seesaram, Emma Caizergues, Taïssir Marcé.

Description: Access control is a central problem in computer security. Given a security policy and a user request, the access control specifies whether (or not) the request should be granted. This has been formalized back in the seventies (see [1]). One of the relevant questions is: given a security policy, does it prevent a user to get unexpected privileges ?

Pedagogical objectives:

  • Working together, on a shared project.
  • Improve the communication
  • Improve the scientific workplan
  • Improve scientific papers reading
  • Marginaly, learn new notions

Planning: The group will meet every Tuesday at 2pm, starting Nov. 16th.

Organization: It would be interesting to first investigate examples of (unexpected) attacks, in order to have a better understanding of what is important and why. A suggestion is to first search for such examples and share them. Another track consists in studying the formal models (see for instance [2]), and criticize their relevance w.r.t. the examples.

  1. M. A. Harrison, W.L. Ruzzo and J. D. Ullman. “Protection in operating systems”, CACM 1976
  2. M. Abadi. “Logic in access control”.
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA