CS-252 Advanced Theoretical Computer Science -- Spring 2013
Course description
The goal of this course is to provide a more in-depth introduction to some of the key ideas in Theory of Computation -- and Theoretical Computer Science at large. Over the semester, we will explore different aspects and manifestations of computing, as well as, develop a set of mathematical tools enabling us to reason about its nature.
The list of topics that we want to cover includes:
Prerequisites
- Fundamental models of computation (finite automata and Turing machines);
- Basics of computational complexity (class P and NP, theory of NP-completeness, P vs. NP problem, other complexity classes);
- The power of randomness and interaction (probabilistic complexity classes, interactive proofs, zero-knowledge proofs, PCP theorem, pseudorandomness);
- Nature-inspired models of computation (quantum computing);
Discrete Mathematics (1st year), Algorithms (2nd year), and mathematical maturity, i.e., ability to read and write mathematical proofs.
Also, this course is a co-requisite for "Theoretical Computer Science" course, thus it will be assumed that the material being covered in that course is known.
TextbooksAlso, this course is a co-requisite for "Theoretical Computer Science" course, thus it will be assumed that the material being covered in that course is known.
There will be no official course textbook -- instead there will be lecture notes available within a couple of days of each lecture.
If one is looking for some supplementary reading then we recommend two positions:
Time and place - "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. This is an excellent book that covers a whole range of topics in computational complexity. It might be, however, slightly challenging for beginners. A draft of this book is available for free here.
- "The Nature of Computation" by Cris Moore and Stephan Mertens. This position provides a great high-level perspective on the material presented in the course.
Lectures - Thursdays 10:15-12:00 in INM 202.
Exercise sessions (following the lectures) - Thursdays 12:15-13:00 in INM 202 and INM 203
Teaching staff
Lecturer: Aleksander Mądry (aleksander.madry@epfl.ch), office hours: Mondays 13:30-15:30, INJ 113 or by appointment.
Teaching assistant (TA): Christos Kalaitzis (christos.kalaitzis@epfl.ch), office hours: Wednesdays 14:00-16:00, INJ 110.
Questions regarding problem sets and the material, in general, should be sent to atcs2013-staff@listes.epfl.ch
Grading
The grade will be based on three in-class exams during the semester [75%] and six problem sets [25%].
Class participation (e.g., interaction during the lecture, asking good questions) can also (positively) influence your grade.
More on: Exams
All three exams will happen during the semester. Each exam will be focused on the material that was covered in the roughly one-third of the course since the previous exam.
Exam dates will be confirmed two weeks in advance; as soon as the date is confirmed, anyone who has a conflict must let Prof. Mądry know of it immediately (for last-minute emergencies, you will need to present documentation, such as a medical certificate) -- for each exam, arrangements will be made for one (and only one) makeup exam, if necessary. The exams are open-book, open-notes, but no electronic devices (cell phones, tablets, e-readers, laptops) are allowed. Each exam will take the place of a lecture.
Problem setsExam dates will be confirmed two weeks in advance; as soon as the date is confirmed, anyone who has a conflict must let Prof. Mądry know of it immediately (for last-minute emergencies, you will need to present documentation, such as a medical certificate) -- for each exam, arrangements will be made for one (and only one) makeup exam, if necessary. The exams are open-book, open-notes, but no electronic devices (cell phones, tablets, e-readers, laptops) are allowed. Each exam will take the place of a lecture.
There will be a total of six problem sets (roughly one problem set every two weeks).
All solutions should be submitted (via course Moodle) as a PDF (typeset in LaTeX, not scanned, except for figures). For your convenience, there will be a template accompanying each problem set (as a .zip archive) - please use it. (These templates will be crafted individually for each problem set, so please do not reuse the templates from other problem sets.)
Here are the guidelines:
All solutions should be submitted (via course Moodle) as a PDF (typeset in LaTeX, not scanned, except for figures). For your convenience, there will be a template accompanying each problem set (as a .zip archive) - please use it. (These templates will be crafted individually for each problem set, so please do not reuse the templates from other problem sets.)
Here are the guidelines:
- Please submit your solutions as a one file with the name in the format: X_psetY.pdf, where X is your last name and Y is the numer of the problem set. Don't forget to update the relevant part of the LaTeX template with your name and possibly the name of your collaborator - see the source of the main template file for specific instructions;
- Problem sets that are submitted late (but no later than three days after the deadline) will receive half credit. After that time, no credit will be given;
- Collaboration with one other person is allowed, but: (1) the writeup of all the solutions has to be prepared independently (in particular, you should understand and be able to explain everything that is written in your solution); (2) in your writeup, you should include the name of your collaborator.
- You can use any source at your disposal (i.e., Google is your friend), but you have to acknowledge everything that you use and you need to write it up in your own words. (This will not lower your grade.);
- Please be precise and (reasonably) formal. Keep in mind that most of the problems ask you to provide a proof of a statement (as opposed to, say, just to provide an example). Therefore, make sure that your reasoning is correct and there are no holes in it. A clear description of how you tried to solve a problem and failed will always earn partial credit, while a solution that is hard/impossible to decipher/follow might not (even if it is in principle correct).
- Avoid using code in your solutions. A brief plain-text description of an algorithm is much better (as long as, it is sufficiently precise and contains all the important details);
- Please be concise. All the problems have solutions whose all details should comfortably fit on one typeset page. If yours does not, you most likely are overlooking some simplification;
- You do not need to reprove anything that was shown in the class (including the "Theoretical Computer Science" one) - just state clearly what was proved and where (pointing to specific parts of the lecture notes works best);
Announcements:
- Lecture notes and problem sets can be downloaded via course Moodle.
- There will be no exercise session in the first week.
Schedule:
- February 21, 2013: What it will all be about (and why you might care). Finite automata. Discussion of types of questions we will be exploring, Deterministic Finite Automata (DFAs);
- February 28, 2013: What you can do with finite memory. Closure properties of regular languages, Non-deterministic Finite Automata (NFAs);
- March 7, 2013: What you cannot do with finite memory. Equivalence of NFAs and DFAs, Pumping Lemma;
- March 14, 2013: What you can (and cannot) do with a little bit more memory. Streaming algorithms;
- March 21, 2013: Time and Computation. Introduction to time complexity classes, the class P;
- March 28, 2013: Exam I. Thursday, March 28, 10:15-13:00, room INM 202. Material covered: finite automata, regular languages, basics of streaming algorithms;
- April 4, 2013: Spring break (no lecture).
- April 11, 2013: Guess and Verify. The class NP and the P vs. NP question;
- April 18, 2013: Power of Randomness. Randomized complexity classes;
- April 25, 2013: Power of Interaction. Interactive and zero-knowledge proofs;
- May 2, 2013: How to Reduce Randomness. Pseudorandomness, One-way functions;
- May 9, 2013: Ascension Day (no lecture).
- May 16, 2013: Exam II. Thursday, May 16, 10:15-13:00, room INM 202. Material covered: time and space complexity classes (especially, the classes P, NP and PSPACE), theory of NP-completeness, randomized complexity classes;
- May 23, 2013: Quantum Computing. Qubits, Quantum measurements and transformations, Entanglement and EPR paradox, Deutsch-Jozsa algorithm;
- May 30, 2013: Exam III. Thursday, May 30, 10:15-13:00, room INM 202. Material covered: Definitions of the classes P, NP, BPP, RP, co-RP, ZPP and PSPACE and known relationships between them, interactive and zero-knowledge proofs, pseudorandomness and one-way functions, basics of quantum computing;