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. 13th, 2022 in room 1Z53 at ENS Paris-Saclay.

Organization:

Sept. 13th, 2PM: Introduction to the course & description of available workshops.

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

Sept. 16th afternoon: Assignment of students to groups announced.

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

Nov. 15th, 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).

Short workshop(s) for first session, starting Sept. 20th, 2022

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

Superviser: Thomas Chatain

Room: 1-K-82 in bâtiment Est

Participants: (7) Florent KRASNOPOL; Maena QUEMENER; Guilhem TURBIAU; Erwann LOULERGUE; Laurent HOLIN; Jean ABOU SAMRA; Yajur PHULLERA

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. 20th, 2022.

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 SA2 “When does a local quantum gate commute with its neighbour?” / P. Arrighi

Superviser: Pablo Arrighi

Room: 1-P-82 in bâtiment Est

Participants: (10) Mina HORCH; Pierre GAILLARD; Mathis DEGRYSE; Gaspard REGHEM; Thomas DELÉPINE; Yoan BOUNIARD; Letao WANG; Balthazar PATIACHVILI; Hubert DE GROOTE; Léo SOUDANT

Keywords: Quantum computing; Cellular Automata, Linear Algebra.

Description: Quantum cellular automata consist in a grid of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same).

Quantum cellular automata provide a model/architecture for distributed quantum computation and quantum simulation. I will quickly review the topic and soon focus on a structure theorem, which states that the global evolution G actually decomposes into a finite-depth circuit of local quantum gates, which commute with one another. Next, in an attempt to refine that theorem even further, we will all try to understand when it is that two neighbouring local quantum gates actually commute with one another.

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

Planning: Six meetings on Tuesdays, 14h-16h, starting 20th of Sept., 2022.

Grading: Based on participation/contribution.

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

Superviser: Laurent Fribourg

Room: 1-Q-82 in bâtiment Est

Participants: (9) Hélène HAN; Pauline BONNET; Audric BESNAULT—CLÉRICE; Vivien DUCROS; Thomas VARIN; Ewen BROUDIN—CARADEC; Linghao ZENG; Adame ABDELAZIZ; Valentin DENÉE

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 Sep. 20th, 2022.

  • 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 SA4 “Type Systems and Programming Languages” / V. Zamdzhiev

Superviser: Vladimir Zamdzhiev.

Room: 3-U-42 in bâtiment Nord

Participants: (10) Shengyu HUANG; Léopold BRASSEUR; Serge LECHENNE; Arthur ADJEDJ; Vincent LAFEYCHINE; Lucas TABARY-MAUJEAN; Rui LI; Colin BLAKE; Maxence PERION; Abdelkader BELLOUNDJA

Keywords: Programming Languages, Type Systems, Logic, Quantum Programming, Probabilistic Programming.

Description: The goal of this workshop is to study and identify advanced and cutting-edge features in programming languages and related type systems. Modern research in programming languages and type systems has produced many interesting new programming features and abstractions that have not yet been introduced into mainstream languages. Students will have the opportunity to dive into modern programming language research and identify specific topics that are of interest to them. Examples can include studying programming abstractions (e.g., monads, dependent types, higher-order polymorphism), more specialised programming languages (e.g., probabilistic programming languages, quantum programming languages), static analysis tools/frameworks, etc. After initial discussion, we will agree on a group project and the students are expected to work together towards its realisation. Possibilities for a group project include: writing a literature review on a specific area of programming language research; identifying interesting open problems; understanding in depth of a specific topic; novel presentation/view of a known idea, etc.

Expected Workload: About 5 hours per week.

Planning: Six meetings on Tuesdays 14h-16h, starting Sept. 20, 2022.

Grading: Details to be discussed, but it will be determined by class participation, contribution and presentation.

Short workshop(s) for second session, starting Nov. 15th, 2022

WG SB1 “State complexity of languages closed by subwords” / Ph. Schnoebelen

Superviser: Philippe Schnoebelen.

Room: 1-K-82 in bâtiment Est

Participants: (10) Mina HORCH; Thomas DELÉPINE; Yoan BOUNIARD; Maxence PERION; Guilhem TURBIAU; Balthazar PATIACHVILI; Abdelkader BELLOUNDJA; Vivien DUCROS; Adame ABDELAZIZ; Laurent HOLIN

Keywords: Finite-state automata, regular languages, descriptive complexity.

Description: State-complexity is concerned with the cost of describing regular languages by various forms of automata. The cost is mainly measured by the number of states. A typical result in this field is that constructing a DFA (deterministic finite-state automaton) for the complementation, the intersection or the union of languages given by DFAs always leads to a result of quadratic size (even linear for complementation) while some other operations (e.g. concatenation) may involve an exponential blow-up.

The goal of this workshop is to provide such state-complexity results when one only considers languages closed by subwords and, a bit more generally, acyclic automata (i.e., DFAs without cycles, only self-loops).

The motivation for these questions comes from the automatic verification of communication protocols for which some existing tools compute with languages closed by subwords. Here the existing methods use simple regular expressions for computing on subword-closed languages and it could be interesting to use DFAs instead.

Part of this workshop will consist in surveying the vast literature on state complexity and see if it already contains some results that answer some of our questions. Another part will consist in proving some upper and lower bounds for the new problems we have singled out. This is the occasion to learn about some fundamentals of automata theory. We'll use the starting problem as motivation for reading papers, presenting key 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 will be successful if we raise some interesting open problems. It is not required that we manage to solve all of them.

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

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

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.

Bibliography: I was involved in the following recent paper that provides results on related topics. Its introduction lists some starting references on the field of state complexity. The paper itself is a good example of the kind of techniques we'll probably use.

WG SB2 “The Art of Reviewing” / D. Berwanger

Superviser: Diermar Berwanger.

Room: 1-P-82 in bâtiment Est

Participants: (9) Vincent LAFEYCHINE; Lucas TABARY-MAUJEAN; Mathis DEGRYSE; Gaspard REGHEM; Hélène HAN; Pauline BONNET; Hubert DE GROOTE; Ewen BROUDIN—CARADEC; Jean ABOU SAMRA

Keywords: Peer-Reviewing; Publishing.

Description: Reviewing is a key element of the publication cycle. The reviewer is the first reader of a paper, he is called to point out ambiguities or mistakes, suggest improvements, and finally judge whether the underlying research effort was successful.

Pedagogical objective: The goal of this workshop is to learn how to write a good review, and how to defend your evaluation in discussions with other reviewers. Towards this, we set up a program committee (PC) for a mock conference, read and evaluate research papers proposed by the instructor, and defend our arguments in discussions with other PC members. Finally, each participant will give a short presentation on one of the reviewed contributions.

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

Grading: Paper synopsis (20%), review reports (30%), PC discussion (20%), talk on your favourite paper (20%), questionnaire (10%).

WG SB3 “Scientific watch for logics in AI” / S. Demri

Superviser: Stéphane Demri.

Participants: (8) Léopold BRASSEUR; Arthur ADJEDJ; Pierre GAILLARD; Audric BESNAULT—CLÉRICE; Letao WANG; Valentin DENÉE; Yajur PHULLERA; Thomas VARIN

Room: 1-Q-82 in bâtiment Est

Description: The goal of this workshop is to study articles published in 2022 in the major AI conferences and workshops about logics dedicated to knowledge reasoning. Knowledge logics form a family of logical formalisms dedicated to represent knowledge and to reason about it. These include epistemic logics, deontic logics, dynamic logics, description logics, strategy logics, temporal logics, etc. We shall discuss questions related to scientific watch, critical analysis of recently published articles, conference program committees rules, etc.

Pedagogical objectives Based on freshly published articles in AI, we discuss general questions about scientific watch. Presentation of articles in 10min and presentation in 30 minuts are expected from the students. Any question related to the relevance of the works, to their originality or their correctness shall be also discussed.

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

Grade 50% is based on the general participation to the workshop, 50% is based on two presentations (10min + 30min, details to be discussed).

WG SB4 “Mathematics, proofs, and computations” / G. Melquiond

Superviser: Guillaume Melquiond.

Room: 3-U-42 in bâtiment Nord

Participants: (9) Shengyu HUANG; Serge LECHENNE; Florent KRASNOPOL; Rui LI; Colin BLAKE; Maena QUEMENER; Erwann LOULERGUE; Linghao ZENG; Léo SOUDANT

Description: In 1998, after several years of research, Thomas Hales proved Kepler's conjecture on sphere packing. His proof was 250-page long and came with several gigabytes of data. Despite a panel of 12 referees, the proof could never be verified in its entirety, thus letting people wonder whether the conjecture had actually been proved. This sorry state led Hales to start a new project: a formalized (i.e., computer-checked) version of his proof. The project succeeded in 2015, and was documented in 2017 in the paper “A formal proof of Kepler conjecture”. This paper will serve as a starting point to discuss what research also entails and all the auxiliary activities that surround it.

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.

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

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

Long workshop(s), from Sept. 20th, 2022 to Jan. 3rd, 2023

WG L1 “Distributed synthetic microbiology” / M. Függer and T. Nowak

Supervisers: Matthias Függer and Thomas Nowak.

Room: 2-Z-41 in bâtiment Nord

Participants: (10) Augustin ALBERT; Esteban CHRISTIANN; Hélène SIBOULET; Antoine GUILMIN-CRÉPON; Roxane VAN DEN BOSSCHE; Guillaume ALEXIS; Tanguy BOZEC; Antonin BRETAGNE; Илья БОВТРЮК; Renwen XU

Keywords: Microbiology; Synthetic biology; Circuit design; Distributed systems

Description: The course is organized as a short research project. It starts with a brief introduction into synthetic biology - 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)

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. 27, 14.00-16.00
    • project talks
  • Oct. 4, 14.00-16.00
  • Oct. 11, 14.00-16.00
    • 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%).

 
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