Table of Contents
Initiation to ResearchIn 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). General PresentationThe “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). Long workshops, from Sep 15th, 2020 to Jan 8th, 2021WG L1 “Intergenerational equity” / S. Le RouxSuperviser: 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. WG L2 “Deciding separation logic” / M. SighireanuSuperviser: 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:
Short workshops for first session, from Sep 15th to Nov 7th, 2020WG SA1 “Distributed synthetic microbiology” / M. FüggerSuperviser: 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:
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.
Grading: Students will be evaluated based on their involvement during team meetings (50%), and final writeup (50%).
WG SA2 “Is discrete geometry of any relevance to relativity?” / P. ArrighiSuperviser: 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%). WG SA3 “Understanding a Research Topic / Practice of State of the Art and Bibliography” / Th. ChatainSuperviser: 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. Short workshops for second session, from Nov 10th, 2020 to Jan 8th, 2021
WG SB1 “Algorithms for compressed texts and files” / Ph. SchnoebelenSuperviser: 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_{0}, F_{1}, F_{2}, .. given by
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. WG SB2 “Verification of Floating-Point Algorithms” / G. MelquiondSuperviser: 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):
WG SB3 “Around a foundational scientific article” / L. FribourgSuperviser: 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:
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:
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 :
Schedule (tentative): Weekly meeting every Tuesday 14h-16h, starting Nov 10th, 2020.
Expected workload: a few hours weekly. Grading: will reflect involvement and quality of contributions. |