- français
- English
Fiches de cours
Computational complexity
CS-524
Enseignant(s) :
Langue:
English
Remark
(pas donné en 2020-21)Summary
In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation. This course advances the students knowledge of computational complexity, and develop an understanding of fundamental open questions.Content
- Complexity classes (time, space, nondeterminism)
- Boolean circuits and nonuniform computation
- Role of randomness in computation (extractors, pseudo-random generators)
- Interactive proofs and zero knowledge proofs
- Probabilistically checkable proofs and their characterization of the complexity class NP (PCP Theorem)
- Communication complexity
Keywords
theoretical computer science
computational complexity
Learning Prerequisites
Recommended courses
Theory of computation (CS-251)
Algorithms (CS-250)
Learning Outcomes
By the end of the course, the student must be able to:- Demonstrate an understanding of computational complexity and the P vs NP problem
- Formalize and analyze abstractions of complex scenarios/problems
- Express a good understanding of different concepts of proofs
- Prove statements that are similar to those taught in the course
- Use and understand the role of randomness in computation
- Illustrate a basic understanding of probabilistically checkable proofs and their characterization of the class NP (the PCP-Theorem)
- Explain recent exciting developments in theoretical computer science
- Compare different models of computation
Transversal skills
- Demonstrate the capacity for critical thinking
- Summarize an article or a technical report.
Teaching methods
Lecturing and exercises
Expected student activities
Actively attending lectures and exercise sessions. Also homeworks and exam.
Supervision
Office hours | Yes |
Assistants | Yes |
Forum | Yes |
Resources
Virtual desktop infrastructure (VDI)
No
Bibliography
Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press.
Ressources en bibliothèque
Websites
Dans les plans d'études
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenPendant le semestre
- Crédits
4 - Matière examinée
Computational complexity - Cours
3 Heure(s) hebdo x 14 semaines - Exercices
1 Heure(s) hebdo x 14 semaines
- Semestre
Semaine de référence
Lu | Ma | Me | Je | Ve | |
---|---|---|---|---|---|
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | |||||
12-13 | |||||
13-14 | |||||
14-15 | |||||
15-16 | |||||
16-17 | |||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
En construction
Cours
Exercice, TP
Projet, autre
légende
- Semestre d'automne
- Session d'hiver
- Semestre de printemps
- Session d'été
- Cours en français
- Cours en anglais
- Cours en allemand