In charge: Ph. Schnoebelen

The working groups start Tuesday Sep 15th, 2020.

Organization:

Sep 10th: working groups descriptions available on this page.

Sep 14thm 9AM: deadline for submitting your preferences (see below).

Sep 14th: Assignment of students to groups announced.

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

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

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.

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

Superviser: Stéphane Le Roux.

Language: French or English as soon as it is better for one student.

Room: MO07 (Mezzanine level)

Keywords: Axiomatic approach to equity; Bibliography.

Description: Is it possible to share resources in a fair way between present and future generations? It all depends on the definition of fairness! An axiomatic approach leads to impossibility results: there are no preference relations over infinite streams of real numbers that satisfy various sets of legitimate axioms. For some sets of axioms there may exist a satisfying preference relation, but its construction may require the axiom of choice. We will start from the 2010 survey Intergenerational equity by Asheim and explore this field that was born around 1960.

We will collectively choose papers to read in small groups and you will present them (including interesting proofs) to the other groups. Eventually you will collectively write a structured summary of the papers, around five pages altogether.

Pedagogical objectives: Writing a bibliography; Teaching each other via oral presentations and written documents; Thinking together via brain storming; Comparing the advantages of different proofs of the same theorem; setting scientific objectives; Summarizing what we know; Sharing the workload in a fair way.

Individual and group expectations: We are a team, i.e., individual work is a basis for collective success.

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

Schedule: weekly meeting every Tuesday 14h-16h, starting Sep 15th, 2020. Please browse the survey “Intergenerational equity” for one hour or two before the first meeting, and bring your laptop.

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

Superviser: Mihaela Sighireanu.

Language: English as soon as one participant is not fluent French speaker. All documents will be in English.

Room: 1X17

Keywords: Hoare logic; Separation logic; Decision procedure.

Description: Separation logic is a logic specifying program's state (or Hoare logic) which is used in academia and industry for the analysis and verification of programs with dynamic memory allocation. Its famous application is the static analyzer Infer, developed by Facebook. This study will concern the automated verification based on separation logic which targets programs with pointer arithmetic. The participants will receive four papers which motivate the verification problem with a practical example and investigate decidable fragments. They will study these papers, understand the proofs and try to find a new decidable fragment or to propose an improvement of the existing decision procedures.

Pedagogical objectives: Working on a corpus of papers and complete it with additional bibliography, understanding complex proofs, presenting them to the group and writing down new versions of these proofs, inventing new techniques, validating them ; working in a research group.

Individual and group expectations: Each participant should contribute with her/his ideas to ensure the success of the group in proposing new techniques.

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

Schedule: weekly meeting every Tuesday 15h15-17h15, starting Sep 15th, 2020.

Grading: 50% for collective involvement during the discussions, and 50% for personal contribution (presenting/writing, looking for new related articles).

Bibliography:

• Separation logic, Peter W O'Hearn, CACM January 2019, https://doi.org/10.1145/3211968
• Beyond Reachability: Shape Abstraction in thePresence of Pointer Arithmetic Cristiano Calcagno, Dino Distefano, Peter W. O’Hearn, and Hongseok Yang, SAS 2006, https://doi.org/10.1007/11823230_13
• Biabduction (and Related Problems) in Array Separation Logic, James Brotherston, Nikos Gorogiannis and Max I. Kanovich, CADE 2017, https://doi.org/10.1007/978-3-319-63046-5_29
• Decision Procedure for Entailment of Symbolic Heaps with Arrays, Daisuke Kimura and Makoto Tatsuta, APLAS 2017, https://doi.org/10.1007/978-3-319-71237-6_9

Superviser: Matthias Függer.

Language: English

Room: 1X74

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)

News:

• 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. 15, 14.00-16.00: Organization and Preliminaries
  • Initial presentation of research area
  • Todo until next time:
    • Write me a subscribe mail

• 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:
    • iGEM http://parts.igem.org/Catalog
  • Single cell:
    • Brophy and Voigt “Principles of Genetic Circuit Design”, Nature Methods, 2014
    • Nielsen et al. “Genetic circuit design automation” Science, 2016
    • Cello compiler http://cellocad.org/about.html
    • 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:
    • Sleight et al. “Designing and engineering evolutionary robust genetic circuits”, Journal of Biological Engineering, 2010. http://www.jbioleng.org/content/4/1/12
  • 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

• Sept. 22, 14.00-16.00: Discussion of research questions in class. Forming groups. 3 groups:

• Genetic circuit compiler (3 researchers)

• Evaluating robustness of a design (3 researchers)

• Wild-type vs. engineered genome (2 researchers)

• Sept. 29, 14.00-16.00: Presentation and discussion of current research state in class. Timeline for next 3 weeks.

• Oct. 6, 14.00-16.00: Presentation and discussion of current research state in class.

• Oct. 13, 14.00-16.00: tba

• Oct. 20, 14.00-16.00: tba

• Oct. 27, group-wise, tba

• Nov. 3, group-wise, tba

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

Superviser: Pablo Arrighi

Language: French by default, English on request

Room: 1X77

Keywords: Bibliography; Concept exploration and comparison; Discrete exterior calculus; Parallel transport; Curvature; Gravity; Digital.

Description: Discrete Geometry is a super active field of Computer Science with a wealth of practical applications. A lot of the theory done on this topic draws its inspiration from continuous geometry, i.e. the study of differentiable manifolds. The study of differentiable manifolds, in turn, owes its main success and popularity to general relativity. Is it possible to reconnect both ends? Are the notions of parallel transport and curvature that were recently developed in Computer Science, close enough to their classical counterparts in the continuous setting, so that they may be relevant to “discretize” aspects of GR, or at least provide good analogies?

Pedagogical objective: Learning a recent theory; Internalizing its main concepts by being able to explain them in simple words; Trying and applying this theory on a new territory.

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

Planning: Tuesday, 14:00-16:00, on Sep 15th, 22nd, 29th, Oct 6th, Nov 3rd, 10th.

Grading: Proactive exploration of the bibliography (20%). Ability to understand new concepts by independently reading about them, and then present them on the whiteboard in a clear and pedestrian manner (60%). Ability to compare concepts from the discrete setting against those of the continuous setting (20%).

Superviser: Thomas Chatain

Language: French by default, English on request

Room: 1Q07

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 Sep 15th. 2020.

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.

Superviser: Philippe Schnoebelen.

Language: English (or French if all participants are fluent enough). All documents will be in English.

Room: 1X74

Keywords: Pattern matching in strings; Algorithms; Formal languages.

Description: Even since file and data compression became a standard way of saving disk space, the question arose of how to search in compressed files without uncompressing them. It turns out that several pattern-matching questions can be answered efficiently (in linear or quadratic time) using dynamic programming and clever tricks.

The goal of this working group is to develop and validate an algorithm for deciding if a compressed text is periodic, i.e. repeats itself like a broken record (sorry for the outdated metaphor), and more generally to identify repetitive parts inside compressed texts.

One can get an idea of the kind of research this involves by e.g. looking at (the beginning of) the survey article by Mark Lohrey: Algorithmics on SLP-compressed strings: A survey, Groups Complexity Cryptology, 4(2):241-299, 2012. Another way to approach the topic is to consider the Fibonacci words F₀, F₁, F₂, .. given by

• F₀ ≝ a ,
• F₁ ≝ ab ,
• F_n+2 ≝ F_n+1⋅F_n

and devise an algorithm that, given n∈ℕ, finds which letter is exactly in the middle of F_n when F_n has odd length. Of course one prefers a solution running in linear time O(n).

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. We could e.g. prove that the problem is NP-hard, or realize that it is not well formulated.

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

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

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.

Superviser: Guillaume Melquiond.

Language: French or English, depending on the participants. Documents will be in English.

Room: 1X77

Keywords: Floating-point arithmetic; Interval arithmetic; Abstract interpretation; Global optimization.

Description: Floating-point arithmetic is ubiquitous nowadays, as it makes it easy to approximate computations on real numbers. Unfortunately, the limited precision might cause the computed numbers to diverge from the ideal results. To ensure the safety of systems, it is thus critical to understand how off a computed result can be. In 2015, Solovyev proposed a novel approach to bounding rounding errors. The goal of this working group is to understand when and why this new method is successful (or not) by comparing it to other approaches, and to invent ways of improving it.

Pedagogical objectives: learn to read scientific papers, to search for untold flaws or hidden gems, to design convincing experiments, to present research works, to argue with other scientists.

Prerequisites: none, as the concepts are quite simple and will be explained during the first session.

Grading: 50% for synthesizing a paper and presenting it, 50% for contributing to the working group's research.

Bibliography: (to be completed as the group progresses):

1. Rigorous estimation of floating-point round-off errors with symbolic Taylor expansions. Solovyev et al. ACM TOPLAS, 2018.
2. Handbook of floating-point arithmetic. Muller et al. 2010, 2018.
3. Certified roundoff error bounds using semidefinite programming. Magron et al. ACM TOMS, 2017.
4. Static analysis of numerical algorithms. Goubault and Putot. SAS, 2006.
5. Taylor expansion of the accumulated rounding error. Linnainmaa. BIT NM, 1976.

Superviser: Laurent Fribourg

Language: French unless English is requested.

Room: 1Q07

Description: Starting from a scientific article that proved to be foundational, the objectives of this working group are:

1. to understand how exactly the article was a breakthrough in his field;
2. to identify some later articles that significantly deepened the breakthrough;
3. to write a survey paper on this line of work.

Pedagogical objectives: The approach is typical of one of the basic tasks a researcher undertakes when s/he is interested in a new research topic and goes through the existing literature in order to:

• identify and synthesize the recent contributions;
• recognize the unsolved problems that are currently blocking further progress;
• come up with new directions where he could contribute.

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

This year foundational articles are :

• Feynman, Richard P. (1986) Quantum Mechanical Computers. Foundations of Physics, 16 (6), pp. 507-531, 1986.
• Shor, Peter W. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52 (4), pp. 2493-2496, 1995.

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

• meeting1 : 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.