M1 20182019
This page gathers useful informations for students following the first year of Master in Computer Science at École Normale Supérieure de Lyon.
The rules for the Master are here. See here for a description of the year.
Internship.
Slides of the meeting of sept. 25th, 2018. Slides of the meeting of jan. 14th, 2019.
The internship defenses will take place on sept. 4th (the whole day) and 5th (in the morning), 2019, at ENS de Lyon. Stay tuned for the schedule of these presentations.
ENSL Diploma.
You can find here the “Livret du diplôme” for the academical year 20182019.
PhDs and PhD grants.
A meeting was organised on november 16th, at 16h15, in amphi B, about PhDs and PhD grants.
Class representants.
Théophile Dubuc and Antonin Dudermel are your class representants this year.
Second semester.
Courses offered: CGDI (David Coeurjolly), DBDM (Emmanuel Coquery et Marc Plantevit), ML (Marc Sebban), SV (Colin Riba), CS (Omar Fawzi), DS (Eddy Caron), CC (Omar Fawzi), PP (Philippe Audebaud), CA (Guillaume Hanrot et Stéphan Thomassé).
Schedule: note that the Integrated Project course will resume its activities on friday, january 25th, at 13.30
Here is the typical schedule. Local changes might apply.
Weekly schedules are available on a shared document — you should have received a link. If not, please write to Suzanne Zeitounian to get the access.
Holidays: 18/0222/02, 15/0422/04 — Final exams: between 23/04 and 30/04, schedule to be defined.
Here is the fiche de choix de modules (choice of courses), to be left in D. Hirschkoff’s “mailbox” before feb. 12th at noon.
First semester.
Courses offered: CAP (Laure Gonnord), IT (Omar Fawzi, TDs), PEN (Éric Thierry, TDs), OA (Nicolas Bousquet), APPD (Anne Benoit), Integrated Project (Eddy Caron).
Here is the typical weekly schedule for the first semester.
Weekly schedules: 1418 jan. – 711 jan. – 1721 dec. – 1014 dec. – 37 dec. – 1923 nov – 59 nov – 2226 oct – 1519 oct – 812 oct – 15 oct 2428 sept 1721 sept. 1015 sept.
Holidays: 29/103/11, and 22/125/1 — Final exams: january 2125, here is the schedule.
Here is the fiche de choix de modules (choice of courses), to be left in D. Hirschkoff’s “mailbox” before sept. 26th at noon.
Midterm exams APPD nov. 5th, PEN nov. 5th, CAP nov. 8th, IT nov 8th, OA nov 20th.
Research schools.
Two research schools are organised, in the weeks 1216 nov. and 2630 nov. During those weeks, no course and no TD in M1 (language courses go on, and you are supposed to attend). See the appropriate web page.
Back to school.
The welcome reception of the Computer Science Department will be on sept. 17th, at 16.00, at the IFÉ (Institut Français de l’Éducation).
A mandatory meeting took place on sept. 10th, at 9h00, in Amphi A. See here the slides of the presentation, and here for slides of the centre de langues.
Students who were at ENSL in L3 in 20172018 did their administrative registration on friday, sept. 7th.
(Français) P2 L3IF — spécification de fouine
(Français) P2 L3IF — débutants Linux
Room booking
Protected: (Français) DRAFT — matériau pour des recommandations pour les stages
M1 20172018
This page gathers useful informations for students following the first year of Master in Computer Science at École Normale Supérieure de Lyon. See here for a description of the M1 year. Here for the rules of the game.
Back to school.
A (mandatory) meeting is organised on sept. 8th, at 9h00, in amphi B. The organisation of the year, and several other relevant topics, will be discussed. There will also be two courses on that day (Integrated Project and Optimisation&Approximation), the second one will finish at 15h30 — see below, “First semester”.
See here about the administrative procedure to register at ENSL. Students who were at ENSL in L3 will register on monday, sept. 11th. There will also be some exercise sessions on that day.
Slides of the presentations (to be provided): general presentation, language department.
A meeting of the whole Département d’Informatique will take place on sept. 18th, at 16.00 at Bâtiment Buisson.
First semester.
Here is the typical schedule for the first semester. Nota: local modifications can occur along the semester.
Here is the schedule for the first courses (sept. 8th15th). Here is the schedule for the week 1822 sept., Here is the schedule for the week 2529 sept., Here is the schedule for the week 26 oct., Here is the schedule for the week 915 oct., Here is the schedule for the week 1622 oct. Here is the schedule for the week 2329 oct. Here is the schedule for the week 610 nov. Here is the schedule for the week 1317 nov. Here is the schedule for the week 2024 nov. Here is the schedule for the week 27 nov.1 dec.
The week 49 dec. will be devoted to a Research School: see here for informations (including the schedule).
Here is the schedule for the week 1115 dec. Here is the schedule for the week 1822 dec.
Here is the “fiche de choix de modules”, to be left in D. Hirschkoff’s mailbox on sept. 26th at noon at the latest.
Holidays: from oct. 28th to nov. 5th, and from dec. 23th to jan. 7th.
CAE sessions (english certification) will be on january 13th, march 24th and june 23rd.
Final exams will take place during the week starting on jan. 8th, 2018. See here for the schedule.
Research schools.
Three research schools will be organised, during the weeks dec. 4th, jan. 15th and jan 22nd. More information here.
Here is the “fiche de choix d’écoles de recherche”, to be left in D. Hirschkoff’s mailbox before november 27th at noon.
Second semester.
Holidays: there will be two weeks of holidays during the second semester, in winter (february 1926) and in spring (april 1623).
Here is the “fiche de choix de modules”, to be left in D. Hirschkoff’s mailbox on feb. 13th at noon at the latest.
Here is the schedule for the week 29 jan – 2 feb. Here is the schedule for the week 59 feb. Here is the schedule for the week 1216 feb. Here is the schedule for the week 26 feb.2 march. Here is the schedule for the week 59 march. Here is the schedule for the week 1216 march. Here is the schedule for the week 1923 march. Here is the schedule for the week 2630 march. Here is the schedule for the week 36 april. Here is the schedule for the week 913 april.
Midterm exams (of which I am aware of, the reference is what the teachers say): CS march 13th, 15.4517.45. SV march 14th, 13.3015.30, CC march 13th, 10.15, DS march 12th, 13.3015.30.
Monday, april 2nd is a holiday (Easter). As a consequence, the CA course that cannot take place will be on wednesday, march 28th, between 18.00 and 20.00. Stay tuned for the DS course that should be on april 2nd.
Final exams will take place in the week 2327 april. The schedule is available here.
Internship.
See the slides of the meeting of oct. 20th, 2017. Stay tuned for some advice about the preparation of the internship contract (remember that the first step from this point of view is to ask whether the hosting institution is willing to sign the contract given by UCBL). Stay tuned also for some advice about the preparation of the internship report and of the defense.
The person in charge of M1 internships is Frédéric Vivien.
Here are the slides of the presentation given on february 12th, 2018.
Some useful files, provided by the bureau des stages: Template internship agreement, aide à la saisie sous Elipse, guide Elipse
Schedule: report due on august 28th, at noon; presentations on september 5th and 6th.
Here is the current version of the schedule for the presentations — make sure to look at it a few days before the presentations, because changes may occur.
Next year.
Most of the M1 students proceed along one of the following paths after validating the M1:
 Study in M2, either at ENS Lyon or somewhere else (in France, abroad).
 Follow a year of preparation for the agrégation de mathématiques.
_{[this is intentionally in french] }Si vous envisagez de préparer l’agrégation de mathématiques l’an prochain, il est conseillé de valider un module de dès cette année. Voir ceci et ceci pour cela.
 Spend a year doing (research) internships, in France and/or abroad.
 Double diplomas (here, and also here for EPFL).
This is something you should keep in mind along the year of M1, and prepare ahead of time.
Means of communication.
The class representants are L. Assouline, S. Fernandez, U. Léchine and P. Oechsel.
Machine Learning
Machine Learning
Course offered in the second semester of the M1.
This course gives a general introduction to Machine Learning, from algorithms to theoretical aspects in
Statistical Learning Theory.
Topics covered:
• General introduction to Machine Learning: learning settings, curse of dimensionality, overfitting/underfitting, etc.
• Overview of Supervised Learning Theory: True risk versus empirical risk, loss functions, regularization,
bias/variance tradeoff, complexity measures, generalization bounds.
• Linear/Logistic/Polynomial Regression: batch/stochastic gradient descent, closedform solution.
• Sparsity in Convex Optimization.
• Support Vector Machines: large margin, primal problem, dual problem, kernelization, etc.
• Neural Networks, Deep Learning.
• Theory of boosting: Ensemble methods, Adaboost, theoretical guarantees.
• Nonparametric Methods (KNearestNeighbors)
• Domain Adaptation
• Metric Learning
• Optimal Transport
Teaching methods: Lectures and Lab sessions.
Form(s) of Assessment: written exam (50%) and project (50%)
References:
– Statistical Learning Theory, V. Vapnik, Wiley, 1998
– Machine Learning, Tom Mitchell, MacGraw Hill, 1997
– Pattern Recognition and Machine Learning, M. Bishop, 2013
– Convex Optimization, Stephen Boyd & Lieven Vandenberghe, Cambridge University Press, 2012.
– Online Machine Learning courses: https://www.coursera.org/
Expected prior knowledge: basic mathematics and statistics – convex optimization
Diploma ENS de Lyon
M1 20162017, useful information
This page gathers useful informations for students following the first year of Master in Computer Science at École Normale Supérieure de Lyon. See here for a description of the M1 year. Here for the rules of the game.
Back to school.
A (mandatory) meeting is organised on sept. 13th, at 14h30, in amphi B. The organisation of the year, and several other relevant topics, will be discussed.
Slides of the presentations: general presentation, language department, new diploma of ENSL.
A meeting of the whole Département d’Informatique will take place on monday, sept. 19th, at 16h00, at the Maison des Mathématiques et de l’Informatique (next to the round square which is close to the Monod site of ENS).
First semester.
Here is the schedule for the first courses, starting from september 14th. Here is the typical schedule for the semester. [ Here is the schedule for the week 1923 sept. Here is the schedule for the week 2630 sept. Here is the schedule for the week 37 oct. ]
The schedules of the following weeks will be variations on this one.
Here is the “fiche de choix de modules”, to be printed, signed with your tutor, and given to D. Hirschkoff, before oct, the 4th sept. the 27th, at noon (write an email in advance if you know that you’ll be late, for some reason).
Partiels (midterm exams) and handouts of which I am aware of (beware, this list is not necessarily exaustive — refer to the teachers for the full information): APPD midterm, october 26th, 13h3015h30. APPD homework: to be determined (assignment available on nov. 7th); TI midterm, nov. 4th, 10h1512h15. OA midterm: oct. 25th, 10h1512h15; CAP midterm: oct 24th, 13h3015h30; EPR midterm: nov. 9th.
Holidays will start on saturday, dec. 17th, and end on january 2nd (courses will resume on tuesday, jan. 3rd).
Here is the schedule for the exams for the first semester.
_{[this is intentionally in french] }Si vous envisagez de préparer l’agrégation de mathématiques l’an prochain, il est conseillé de valider un modle de dès cette année. Voir cette page pour cela.
Research schools.
You have to follow and validate at least 2 of the research schools that are offered, in Lyon and Sophia Antipolis. See here for the dedicated webpage.
The fiche de choix d’écoles de recherche, to be given for november 15th, at noon, is available here.
Important notice for the Research Schools organised in SophiaAntipolis: please make sure to register to the school (follow the links to the dedicated webpage). You may ask for help in order to find an accomodation there.
Second semester.
Holidays: there will be two weeks of holidays during the second semester, in winter (february 1926) and in spring (april 1623).
Here is the weekly schedule, as of january 5th. The planned week for the exams is may 1519, some exams may take place in the preceding week. Here is the “fiche de choix de modules”. The deadline is march 7th, at noon.
Projet intégré: sessions on feb. 13th, feb. 27th, mar. 6th, mar. 13th. Demo on april 7th, final meeting on april 10th.
Midterm exams: CS on march 30th, 8.0010.00.
Schedule of the last weeks of teaching : 2428 april, 25 may, 912 may.
Schedule of the final exams: here.
Internship.
Slides of the meeting which took place on october 10th.Stay tuned for a page describing the procedure to prepare the internship contract (convention de stage).
The presentations of the internships will take place on september 5th and 6th, in Lyon.
Next year.
Most of the M1 students proceed along one of the following paths after validating the M1:
 Study in M2, either at ENS Lyon or somewhere else (in France, abroad).
 Follow a year of preparation for the agrégation de mathématiques.
 Spend a year doing (research) internships, in France and/or abroad.
This is something you should keep in mind along the year of M1, and prepare ahead of time.
Means of communication.
The class representants are R. Cerda and T. Sterin.
OLD – M1, convention de stage
The instructions to prepare the internship contract are available only in french. You may ask your internship advisor for some help in order to prepare the contract, in case she/he speaks french. If not, contact D. Hirschkoff.
M1 20152016, useful information
This page gathers useful informations for students following the first year of Master in Computer Science at École Normale Supérieure de Lyon. See here for a description of the M1 year. Here for the rules of the game.
Back to school.
Courses will start on september the 14th. See here for a schedule of that week. A (mandatory) meeting is organised on september 10th, at 15.30, in Amphi I (slides of the presentation, slides about english & other languages). The organisation of the year, and several other relevant topics, will be discussed. The venue will be announced later. There is no dress code. A meeting of the whole Département d’Informatique will take place on monday, sept. the 14th, at 16.00, in atrium Mérieux (not far from the fountain on the round square next to the Monod site of ENS).
First semester.
Here is the typical week for the first semester, which will serve as a reference starting on sept. the 14th. Be aware that along the semester, local changes to the schedule may apply: refer to the emails you receive (typically, on thursday or friday for the following week). Here is the schedule for the first week, 1418 sept. Here is the “fiche de choix de modules”, to be printed, signed with your tutor, and given to D. Hirschkoff.
Midterm exams (beware, this is list is not necessarily exhaustive, and is only there to help you — please refer to the actual course to learn about exams/homeworks/etc.): Information Theory as well as Parallel and Distributed Algorithms and Systems, nov. 9th, Compilers and Program analysis on nov.17th, Performance Evaluation and Networks on nov. 13th nov. 18th, Optimisation&Approximation nov. 20th.
The exams for the first semester will take place in the week jan.2529. Here is the schedule.
Research schools.
M1 students should validate at least two research schools. See this webpage for a list of the research schools proposed in this academical year. Here is the fiche de choix d’écoles de recherche.
Second semester.
The second semester will last between february 1st and april 26th. The exams will take place between april 27th and may 4th.
The schedule for the first weeks is available here. The plan is to organise, after a couple of weeks, some overlap between courses, in order to have thursday afternoon free, and to gain more flexibility in the handling of the schedule.
Here is the fiche de choix de modules, to be given to D. Hirschkoff for february 16th, at noon.
Partiels (be aware that this list may be nonexhaustive, it contains the information I am aware of): computer algebra march 14th / computational complexity march 22nd / cryptography and security march 18th / april 6th: CGDI project due.
Exams : here is the schedule.
Internship.
Here are the slides of the meeting about internship that took place on oct. the 6th, 2015 (nota: we are not sure yet about the date for the defense: it could be end of august or beginning of september).
Important dates:
 march 15th: deadline to apply to ENS fundings for travel (see the slides)
 march 31st: Internship contract data entered in Elipse

april 15th: internship contract sent abroad

may
16th9th: leaving for the internship
The procedure for the preparation of the internship contract (convention de stage) is described here.
Deadlines and advices for the evaluation of the internship: see here.
Modes of interaction, all along the year.
For administrative matters, please contact Amel Zagrarni (secrétariat du Département d’Informatique). To discuss scientific/academical matters, as well as your training period, your future, etc., you can contact your tutor (the list of tutors is here), or Daniel Hirschkoff. Your délégués (representants of the students) are Victor Hublitz, Raphaël Monat and Étienne Moutot. Remember that you are supposed to read your email @enslyon.fr — in case of a technical problem, get in touch as soon as possible with the Direction des Systèmes Informatiques).
Next year
 Préparation à l’agrégation { this information is not relevant if you don’t speak french } : il y a 12 ECTS à valider par le biais de modules de professionalisation.Cette page, qui sera régulièrement mise à jour, décrit l’ensemble des cours qui sont proposés (ainsi que les modalités d’inscription). À noter que cela peut être une bonne idée de valider ces modules l’année qui précède la préparation à l’agrégation, mais on ne peut pas les valider plus d’un an en avance (si vous souhaitez préparer l’agrégation après le M2, c’est en M2 que vous pourrez suivre et valider ces modules).
Les gens qui ont manifesté un intérêt potentiel/hypothétique pour la préparation à l’agrégation l’an prochain sont: Carette Titouan, Combette Guillaume, Faron Maxime, Iannetta Paul, Lajou Dimitri, Lebeau Fabrice, Lucas Christophe, Mauras Simon, Ohlmann Pierre, Perrotin Elise, Seif Johanna  M2: you might be interested in applying for the M2 at ENS Lyon, but maybe also somewhere else, depending on your scientific interests. It is up to you to find out about the corresponding application procedure, and about the dates. Usually applications can be made around mayjune. (You may well apply to several Masters, be accepted in several places, take your decision during the summer, and inform everybody of your choice — including places where you don’t go)
Important notice: alas, it might be the case that you will not validate your M1, or that you validate it but will not be accepted to our local M2. It is up to you to judge whether you run the risk of ending up in this situation or not. It is also up to you to be prepared for all possibilities, and, if applicable, to apply to a different Master, at M1 level. Do it in advance, september is usually too late.
Data Bases and Data Mining
Databases and Data Mining
Course offered in the second semester of the M1.
This course gives a general introduction of data management through relational databases and data mining from algorithms to theoretical aspects.
Topics covered:
Databases:
 Relational model, relational calculus, SQL
 Relational algebra, equivalence between relational calculus and algebra, indexation and optimisation
 Functional dependencies, axiomatisation, Armstrong’s relations
 Inclusion dependencies, data exchange, chase, query rewriting
 Openness to current issues
Data Mining:
 Introduction to data mining (itemset/rule mining, enumeration algorithms)
 constraintbased pattern mining: study of constraint properties and pruning
 Assessment of results (statistical significance, relevancy w.r.t. background knowledge, user prior)
 Advanced pattern mining: formal concept analysis, sequences, graphs, dynamics graphs, attributed graphs
 Clustering: general aims, distances, similarities, algorithms (kmeans, EM, densitybased clustering, spectral clustering, hierarchical clustering), graph clustering
 Anomaly detection
 Current issues and challenges
Teaching methods: Lectures and Lab sessions (TP).
Form(s) of Assessment: written exam (50%) and project(s) (50%)
References:
 M. Levene, G. Loizou. A Guided Tour of Relational Databases and Beyond. Springer, 1999.
 I S. Abiteboul, R. Hull et V. Vianu. Fondements des bases de données. AddisonWesley, 1995.

I R. Ramakrishnam et J. Gehrke. Database Management Systems. 2003 (third edition).
Material available on pages.cs.wisc.edu/~dbbook/)
 On line course: https://cs.stanford.edu/people/widom/DBmooc.html
 Charu C. Aggarwal, Data Mining, Springer, 2015.
 Mohammed J. Zaki, Wagner Meira, Jr. Data Mining and Analysis Fundamental Concepts and Algorithms. Cambridge University Press, 2014.
Expected prior knowledge:
Link:
https://perso.liris.cnrs.fr/ecoquery/dokuwiki/doku.php?id=enseignement:dbdm:start
Distributed Systems
Distributed Systems
Course offered in the second semester of M1.
Course contents:
Abstract: In this class, through many examples and training we will discover the main distributed algorithms. From the modelization to the implementation. Wave Algorithms, Transversal Algorithms, Leader Election, Mutual Exclusion are introduced.
In a second part of the class we will focus on an advanced distributed systems approach (this advanced part change over the years). We built distributed system using Erlang during the practical sessions. A distributed middleware will be introduced too.
Prerequisites:
Basic knowledge in algorithmics.
Teaching material:
Slides will be published in a private room due to the fact than updates are usual.
Semantics and Verification
Sémantique et Vérification
The goal of formal verification is to check automatically that some programs or systems
are correct with respect to their requirements.
In this course we present mathematical models of programs and systemsand we
describe classes of properties which can be automatically checked on these models.
Content of the course:
 Modelling with Labelled Transition Systems
 LinearTime Properties
 Definition and Examples
 Characterizations via Order Theory and Topology
 ωRegular Properties and Büchi Automata
 Linear Temporal Logic
 Bisimulation and Modal Logic
 Bisimulation and Trace Equivalence
 HennessyMilner Logic
 Bisimulation and Logical Equivalence
The course follows parts of the book: Baier, C. and Katoen, J.P., Principles of Model Checking, MIT Press, 2008.
Prerequisites:

We assume some familiarity with automata theory and mathematical logic, essentially
corresponding to the courses Fondements de l’informatique and Logique given in the
L3 year of the Computer Science Department of the ENS de Lyon.
Proofs and Programs
Proofs and Programs
Contents of the course.
“Reasoning and programming are the two sides of the same coin”.
The core of this relation relies on the discovery of a very deep correspondence between Gentzen presentation for proofs of elementary statements from propositional calculus and typing Church’s λterms, named CurryHoward correspondence (1980). Since then, the correspondence has been widely extended, which led toward powerful proof assistants and finer understanding of mathematical proofs; and correctness of programs as well.
Yet, until recently, equality was not properly understood, leaving on one side major mathematical techniques (congruences, quotients, …). In 2006 [Vladimir Voevodsky](Vladimir Voevodsky) envisioned a connection between equality proofs and homotopy. Since then, the relation between proofs and programs has regained a huge amount of attention. Recently (2015), a first contribution to providing a computational interpretation to the extended Type Theory HoTT has been proposed. We get closer to be able to do maths by programming!
References.
 Lectures on C.H. isomorphim, by M. H. Sørensen and P. Urzyczyn.
 Homotopy Type Theory, collaborative book (http://homotopytypetheory.org/)
Prerequisites.
 Logic (mainly Proof Theory, as opposed to Model Theory)
 Basics in Lambdacalculus
Webpage of the course: https://perso.enslyon.fr/philippe.audebaud/PnP/
Image processing, digital and computational geometry
Image processing, digital and computational geometry
Course offered in the second semester of M1.
Objectives of the course:
The objective of this course is to introduce fundamental notions of image processing, digital geometry and computational geometry. The first lectures will be dedicated to image processing (filtering, smoothing, morphological mathematics, ..) and shape representation. Then, we will focus on theoretical and algorithmic issues involved in the analysis of digital shapes. During this analysis of digital geometry processing tools, we will have to present and integrate some tools from various fields: discrete mathematics, combinatorics, arithmetics, computational geometry, ..
Course contents:
 Image/Shape representation
 Image processing (filtering, segmentation)
 Digital Geometry for shape analysis
 Computational geometry and data structures
 Requirements: basic notions of algorithmics
References:
 Géométrie discrète et images numériques, D. Coeurjolly, A. Montanvert and J.M. Chassery, Ouvrage collectif, Traité IC2, Hermès, 416 pages, 2007
 Digital Geometry: Geometric Methods for Digital Picture Analysis, Reihnard Klette, Azriel Rosenfeld, Morgan Kaufmann, 2004
 Computational Geometry: Algorithms and Applications, Mark de Berg, TU Eindhoven (the Netherlands) Otfried Cheong, KAIST (Korea),Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands), SpringerVerlag
Computational Complexity
Computational Complexity
Course offered in the second semester of M1.
Overview of the course:
Computational complexity aims to classify computational problems depending on the resources they need. One
studies various modes of computation such as deterministic, randomized, nondeterministic or quantum and compares
resources such as time or space needed to solve algorithmic problems. The objective of this course is to give a
broad understanding of the notions used to classify computational problems. About half of the course is dedicated
to studying basic complexity classes defined using Turing machines. We introduce (or study deeper) notions that are
central in complexity theory: nondeterministic computation (e.g., the class NP), reductions between computational
problems (e.g., NPcompleteness) and the technique of diagonalization (e.g., hierarchy theorems). We also study
randomized computation and computation using boolean circuits as well as their relation to basic complexity classes.
We conclude the course by studying the complexity of communication, i.e., trying to evaluate communication
bottlenecks to perform a given computational task between different parties.
Teaching in 2014: Omar Fawzi (lectures) and S ́ebastien Maulat (exercise classes)
Course objectives:
One can summarize the most important objectives of the course as follows.
 Understand the formal definitions for the basic complexity classes like L, NL, P, NP, coNP, PSPACE.
Be familiar with nondeterministic computation and the polynomial hierarchy. Know about the inclusions and separations between these classes.  Understand the notion of reduction between computational problems, and the notion of complete problem, e.g., SAT is NPcomplete, PATH is NLcomplete, TQBF is PSPACEcomplete.
 Understand complexity classes defined using boolean circuits, and the notion of uniformity in computation. Know the relation to basic complexity classes.
 Understand complexity classes using randomized computations. Know the relation to basic complexity classes.
 Get a flavour for the power of interactive proofs.
 Be familiar with an important tool in theoretical computer science: communication complexity. Be able to reduce various problems to a communication complexity problem.
Cryptography and Security
Cryptography and Security
Course offered in the second semester of M1.
Course contents:
This course is an introduction to the different facets of modern cryptography.
The following topics will be addressed:
 Symmetric cryptography
Pseudorandom number generators
Pseudorandom functions
Message Authentication Codes
Stream ciphers and block ciphers
Security against chosen plaintext/ciphertext attacks
Hash functions  Asymmetric cryptography
Discrete logarithm, decision DiffieHellman
Factoring, RSA problem
Key exchange
Digital signatures
Publickey encryption
The random oracle methodology  Other topics possibly covered:
Zeroknowledge proofs
Secret sharing
Yao’s garbling circuits
Computer Algebra
This class shall survey some of the central topics of computer algebra
: arithmetics, effective linear algebra, polynomial system solving.
The following topics will be studied :
I. Arithmetic(s) — mostly polynomial.
– Representation of polynomials, linear operations (addition, evaluation).
– Multiplication : schoolbook method, Karatsuba method, ToomCook method
Fast Fourier Transform.
– Division : schoolbook method, Newton method, recursive division
– GCD : Euclidean algorithm, extended GCD, application to CRT; introduction
to fast GCD.
– Fast multiple point evaluation, fast interpolation, fast CRT.
II. Linear algebra over a field
– Matrix/vector product, naive matrix/matrix product
– Row echelon form & applications : kernel, image, rank, determinant,
linear system solving, etc.
– Fast matrix/matrix product : Strassen ; fast inversion/determinant.
– Structured matrices: circulant, Hankel, Toeplitz, Cauchy, and related
algorithms.