Informations M2 – 2018/2019

General Outline

The Master 2 in Computer Science is composed of classes and winter schools from September 10, 2018 to January 25, 2019, followed by an internship from January 28 to June 15, 2019. See details below.

Latest Information

Updated schedule and latest info available on the read-only password-protected pad (handed out during the pre-course meeting):

https://pad.inria.fr/p/r.7e3a9396c0b060bfc755a346325a79f2

List of Courses (for full description follow the link CRxx):

  • CR01: Optimal Decision Making and Online Optimization, Panayotis Mertikopoulos and Bruno Gaujal (Grenoble).
  • CR02: Computational Geometry, Monique Teillaud and Olivier Devillers (Nancy).
  • CR03: Hard lattice problems, Damien Stehlé. (Lyon)
  • CR04: Scheduling at scale, Yves Robert. (Lyon)
  • CR05: Advanced Topics in Scalable Data ManagementEddy Caron and Marcos Dias de Assuncao. (Lyon)
  • CR06: Software Engineering & Compilation, Sebastien Mosser and Laure Gonnord (Lyon, Nice).
  • CR07: Complex NetworksMarton Karsai. (Lyon)
  • CR08: Lower bound methods, Pascal Koiran, Omar Fawzi, and Stéphan Thomassé (Lyon)
  • CR09: Approximation Theory and Proof Assistants: Certified Computations, Nicolas Brisebarre and Damien Pous (Lyon)
  • CR10: Cryptanalysis, Elena Kirshanova, Damien Stehlé, and Guillaume Hanrot (Lyon)
  • CR11: Hardware Compilation and Simulation, Christophe Alias and Matthieu Moy (Lyon)
  • CR12: Combinatorial scientific optimization, Bora Ucar, Fanny Dufossé (Lyon, Grenoble)
  • CR13: Topological combinatorics, Frédéric Meunier and Matěj Stehlík (Paris, Grenoble)
  • CR14: Advanced topics in semantics of programming language, Pierre Clairambault and Colin Riba (Lyon)
  • CR15: Logic, Automata and Games for Advanced Verification, Matteo Mio and Denis Kuperberg (Lyon)
  • CR16: Automated Deduction, and opening to Distributed Algorithms, Xavier Urbain and Sébastien Tixeuil (Lyon, Paris)
  • CR17: Machine learning, Aurélien Garivier (Lyon)

Winter Schools:  There are two winter schools taking place during weeks 48 (starting on Monday, Nov. 26) and 49 (starting on Monday, Dec.  3) . During these weeks, the courses stop and are replaced by the schools, which last the whole week. Topics will be announced later on.

Pre-course Meeting: A pre-course meeting will take place on Monday, September 10, 2018 at 9.30am, Amphi B. Attendance to this meeting is mandatory for all students. The general organization of the year and a description of the courses will be provided. Courses start on Monday, September 10, at 1:30pm.

Training Period: A mandatory training period takes place from Monday, January 21 up to mid June. An information session about topics and locations for the training period will be organized in September. Basically, the goal is to research in a laboratory (anywhere on earth), write a report and make an oral presentation in the end.

Schedule: Courses start September 10 at 1:30pm. Autumn holidays are October 27-November 4. Winter holidays are December 22-January 6. Exams will be held on week 3 (starting Monday Jan. 14), for a subset of courses. Again, the detailed weekly schedule will be available on the Inria pad mentioned above. This page will be read-only and updated on a regular basis, check it often.

Rules of the Game: To obtain their degree, CS Master students must complete 60 credits including the internship (30 credits), two winter schools (3 credits each) and four courses (4 credits each) in the above list of CR1 to CR17. To summarize, there are 52 mandatory credits out of 60 and 8 credits that can be picked elsewhere. While a typical choice by many students is 6 CR courses, 2 schools and the internship, the extra courses for the 8 credits can be chosen elsewhere,  e.g. CS courses in the M2 offered by Univ. Lyon 1, or courses from other ENS departments.

Complex Systems: There is an exception for the orientation ‘Complex Systems’. See details at

http://www.ixxi.fr/enseignement/master_systemes_complexes

for course offering. For the validation, the two winter schools are not mandatory for complex systems students, only 4 CR courses and the training period are mandatory, so after mandatory stuff there remains 14 credits instead of 8  to validate, using a selection of courses from the orientation.

Note that ‘Complex Systems’ is an orientation, not a separate M2. The only diploma delivered by ENS Lyon is M2 Informatique Fondamentale, and computer science must remain at the heart of the curriculum. In particular, the training period must be oriented towards research in core computer science (possibly applied to other disciplines).

Formal Validation: To meet the quality requirements of our program, all course choices must be approved by the academic tutor and the head of the Master 2 program. Administrative registration to chosen courses is mandatory and takes place in late September, after a trial period.

Please refer to the rules of the Master here

Contact: Yves Robert

Information M2 – 2017/2018

List of courses (for full description follow the link CRxx):

  • CR01: Optimal Decision Making and Online Optimization, Panayotis Mertikopoulos and Bruno Gaujal.
  • CR02: Computational Geometry, Monique Teillaud and Olivier Devillers.
  • CR03: Hard lattice problems, Damien Stehlé.
  • CR04: Automata, coinduction, and relation algebra, Damien Pous.
  • CR05: Monadic Second Order Logic, Automata, Expressivity and DecidabilityMatteo Mio and Denis Kuperberg.
  • CR06: Implicit Computational Complexity, Patrick Baillot and Olivier Laurent.
  • CR07: Models of concurrency, categories, and games, Pierre Clairambault and Glynn Winskel.
  • CR08: Scheduling at scale, Yves Robert.
  • CR09: Advanced Topics in Scalable Data ManagementEddy Caron and Marcos Dias de Assuncao
  • CR10: Software Engineering & Compilation, Sebastien Mosser and Laure Gonnord 
  • CR11: Mathematical Methods for Image SynthesisNicolas Bonneel and Julie Digne.
  • CR12: Modeling and performance evaluation of computer and communications system, Philippe Nain.
  • CR13: Computational TopologyFrancis Lazarus and Arnaud de Mesmay.
  • CR14: Network Information TheoryJean-Marie Gorce and Samir M. Perlaza. Sorry, this course will not open this year but later in 2018-2019.
  • CR15: Complex NetworksEric Fleury and Marton Karsai.
  • CR16: Lower bound methods, Pascal Koiran, Omar Fawzi, and Stéphan Thomassé.
  • CR17: Graph Decompositions: From Tree-Width to Perfect GraphsNicolas Trotignon and Stéphan Thomassé.

Winter schools:  Information will be provided later on. The three schools will take place on week 49 (starting Monday Dec. 4), on week 3 (starting Monday Jan. 15)  and on week 4 (starting Monday Jan. 22).

Pre-course meeting: A (mandatory) pre-course meeting will take place on Monday, September 11 at 9.30am, Amphi B. The general organization of the year and a description of the courses will be provided.

Schedule: Courses start September 11 at 1:30pm. Autumn holidays are October 28-November 5. Winter holidays are December 23-January 7. Exams will be held on week 2 (starting Monday Jan. 8), for a subset of courses. The detailed schedule is available here:

https://pad.inria.fr/p/r.542fa856c4fe21df30b444eb43913405

This page is read-only and password protected (password is ‘m2info17’). The page is updated on a regular basis, check it often.

On Thursday October 12 at 12:15pm, right after the CR15 course, there is a meeting about the training period (or internship). Come ofr information and prepare your questions!

Validation: To obtain their degree, CS Master students must complete 60 credits including the internship (30 credits), three winter schools (2 credits each) and four courses (4 credits each) in the above list. A typical choice is 6 courses, 3 schools and the internship; the extra courses can be chosen either in the CS courses or in the other departments. To meet the quality requirements of our program, the course choices must be approved by the academic tutor and the head of the Master 2 program. Administrative registration is mandatory. Please refer to the rules of the Master here

Contact: Yves Robert

Master 2 – 2016/2017

List of courses (for full description follow the link CRxx):

CR-05 : Modèles de Blum-Shub-Smale et de Valiant

Programme de l’UE

Prouver des bornes inférieures sur la complexité algorithmique de problèmes spécifiques est souvent très difficile.  Par exemple, la question “P=NP ?” est de cette forme: il s’agit d’obtenir une borne inférieure superpolynomiale sur la complexité en temps du problème SAT (ou de manière équivalente sur la complexité de n’importe quel problème NP-complet).  Etant donnée la difficulté de ce problème et d’autres problèmes de ce type, on a proposé des modèles de calculs algébriques, variantes des modèles booléens “standards”; et on espère que les questions analogues soient plus abordables dans ces nouveaux modèles.

Les deux principales versions algébriques du problème “P=NP ?” sont dûes à Valiant et à Blum-Shub-Smale, et sont toujours ouvertes. Par exemple, le contenu algorithmique du problème “P=NP ?” dans le modèle de Blum-Shub-Smale sur le corps des nombres réels est le suivant: étant donné un polynôme dedegré 4 en n variables, peut-on décider s’il admet une racine réelle en un nombre d’opérations arithmétiques et de comparaisons polynomial en n ? Les meilleurs algorithmes connus à ce jour effectuent un nombre d’opérations exponentiel en n.

Dans le modèle de Valiant on ne s’intéresse pas à des problèmes de décision mais à l’évaluation de polynômes. Le contenu algorithmique de la question VP=VNP peut être formulé ainsi: est-il possible d’évaluer le permanent d’une matrice en un nombre d’opérations arithmétiques polynomial en la taille de cette matrice ?

On présentera ces deux modèles de calcul et des approches proposées pour aborder les versions correspondantes du problème P=NP:

  • conjecture tau de Shub et Smale: n! (ou un multiple) ne peut pas se calculer en un nombre d’opérations arithmétiques polynomial en log n
  • La version de cette conjecture sur le nombre de racines entières des polynômes donnés par circuits (qui est supposé polynomial en la taille du circuit).
  • La non généralisation aux racines réelles (polynômes de Chebyshev, exemple de Borodin-Cook).
  • Une version réelle pour les sommes de produits de polynômes creux.

On présentera également des résultats sur la réduction de profondeur pour les circuits arithmétiques, certains anciens (Muller-Preparata, Valiant-Skyum-Berkowitz-Rackoff), d’autres plus récents (Agrawal-Vinay).  Ces résultats sont non seulement intéressants du point de vue du calcul parallèle, mais aussi comme on le verra pour les bornes inférieures.

Prerequis: Il s’agit d’un cours de complexité donc un certain goût pour ce sujet et les connaissances acquises à l’occasion d’un premier cours (par exemple, le cours de complexité algorithmique de M1) ne peuvent pas faire de mal. Mais il n’y aura pas de besoin de connaissances specialisées dans le domaine car le cours porte sur des modèles de calcul alternatifs à la traditionnelle machine de Turing. Si nécessaire, quelques rappels de complexite booléenne seront faits.

Modalités d’examen : exposé sur un article (petit rapport + présentation orale) et examen écrit “classique” à la fin.

Intervenant

  • Pascal Koiran, Pr. ENS Lyon

CR-06 : Approximations : from symbolics to numerics, with applications.

The goal of this course is to describe recent progresses (last 5 years or so) in lattice-based cryptology. Using lattices allows one to build public-key primitives with asymptotic efficiency superior to other existing systems, while providing much more precise security guarantees.

Course outline

  • Euclidean lattices : definitions, properties, algorithmic problems, lattice basis reduction, approximate algorithms
  • Classical lattice-based crypto : GGH, NTRU.
  • Modern techniques : discrete gaussians, smoothing parameter, statistical distance, sampling
  • Algorithmic problems underlying the new cryptographic functions : SIS, LWE
  • Lattice-based cryptographic functions : Hash functions, digital signatures, encryption, Identity-Based Encryption, Homomorphic Encryption.

Web page for the course

Lecturers

CR-07 : Scheduling

(This course will be delivered in English on demand)

Scheduling is sub-part of Operation Research, which aims at allocating resources to tasks, and organize their processing, so as to optimize a given objective (which could be total execution time, throughput, etc). In this course, we will study the scheduling problems which appears in computer systems, and in particular on parallel computing platforms.

We will first present the classical scheduling problems and techniques, and gradually introduce models which account for the characteristics of modern computing platforms, and at the same time allow to keep optimization problems tractable. Then, we will present specific objectives for these platforms, as well as the techniques
employed to solve corresponding problems.

Tentative outline:

  1. Classical approaches in scheduling
    • introduction and classical problem (list scheduling, Smith ratio, etc.)
    • application modeling (task graphs, flow-shop, moldable tasks, etc.
    • NP-completeness, approximation algorithms
    • online and non-clairvoyant scheduling
  2. Towards a more realistic model for computing platforms
    • introduction of communication costs
    • divisible load scheduling
    • steady-state scheduling
    • interference-aware scheduling
  3. New objectives and techniques in scheduling
    • fault tolerance and robustness
    • energy-aware scheduling
    • multi-organisation scheduling
    • game theory
    • stochastic approach
    • multi-criteria scheduling

All techniques will be illustrated through case studies.

Evaluation. The evaluation will consist in article analysis and presentation. Some classes will allow the student to practice reading articles and commenting on them.

Pre-requisite: Parallel Algorithm course in M1 (desirable but not essential); for motivated students, studying thoroughly a few chapters of the corresponding book should be enough.

Instructors

  • Loris Marchal, CR CNRS
  • Frédéric Vivien, DR INRIA

CR-09 : Grid & Cloud Computing

Program

This lecture provides an overview as large as possible about the research around the Grid (through different kind of Grid: Grid computing, Research Grid, Production Grid, etc.) We talk about Grid architecture, data management (Hadoop, etc.), middleware, services (SOA, PaaS, SaaS, etc.), the Cloud Computing and so on. Moreover, we will see different programming model as workflow paradigm, software component, skeleton-based programming or the chemical models.  This lecture concerns the second year of the master and will be finish through the study of paper from this research topic by the students.

Lecturers

  • Eddy Caron
  • Christian Perez