CS-459 / 6 credits

Teacher: Chiesa Alessandro

Language: English


Summary

Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science, as well as on real-world secure systems. They underlie delegation of computation protocols and hardness of approximation. This course covers the foundations of probabilistic proof systems.

Content

Learning Prerequisites

Recommended courses

- CS-250 Algorithms
- CS-251 Theory of Computation

 

Important concepts to start the course

- Basic knowledge of discrete probability.
- Basic knowledge of finite fields and their properties.
- Basic knowledge of algorithms (asymptotic notation and analysis of algorithms).
- Basic knowledge of computational complexity (Turing machines; boolean circuits; complexity classes;
reductions, familiarity with the classes P and NP; probabilistic computation and the class BPP).

Learning Outcomes

By the end of the course, the student must be able to:

  • Understand different models of probabilistic proofs
  • Analyze the security of probabilistic proofs protocols and how general computations are probabilistically checked

Teaching methods

Two weekly lectures that include definitions, theorems, and proofs. One weekly recitation to guide students
through exercises. Weekly problem sets to reinforce the material.

Expected student activities

- Attend lectures and participate in class
- Complete homework assignments
- Complete a final exam or final project

Assessment methods

- Class participation (5%)
- Homeworks (55%)
- Exam or project (40%)

Supervision

Office hours Yes
Assistants Yes
Forum Yes

In the programs

  • Semester: Fall
  • Semester: Fall
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Foundation of probabilistic proofs
  • Lecture: 4 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Foundation of probabilistic proofs
  • Lecture: 4 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Semester: Fall
  • Semester: Fall
  • Semester: Fall
  • Semester: Fall
  • Semester: Fall
  • Semester: Fall
  • Exam form: During the semester (winter session)
  • Subject examined: Foundation of probabilistic proofs
  • Lecture: 4 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks

Reference week

 MoTuWeThFr
8-9     
9-10     
10-11     
11-12     
12-13     
13-14 INM201INM201  
14-15   
15-16  INM201  
16-17     
17-18     
18-19     
19-20     
20-21     
21-22     

Tuesday, 13h - 15h: Lecture INM201

Wednesday, 13h - 15h: Lecture INM201

Wednesday, 15h - 16h: Exercise, TP INM201