PCP and inaproximability, notes tutorial13.pdf (the solutions contain literature for that)
Min sketch from Section 5.4 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf
We will finish the gap preserving reductions and hardness of approximation next time: chapter 16 (has section on max label cover) of The Design of Approximation Algorithms (Williamson, Shmoys) available online
Hashing, uses etc tutorial11.pdf.
Derandomization, Yao, hash functions tutorial10.pdf.
Electrical networks theory tutorial9.pdf.
Coupling again, intro to streaming algorithms.
Problems from tutorial8.pdf
Homework 2 hw2.pdf, by May 16
Matchings, IP protocol for permanent.
Problems from tutorial7.pdf
Counting, permanents and determinants, matchings.
Problems from tutorial6.pdf
Equivalence of norms (inequalities with Euclidean and Manhattan norm), coupling lemma and mixing time on a hypercube.
Problems from tutorial5.pdf
First three problems from tutorial4.pdf
Next tutorial we start with the fourth problem. You might want to review Courant-Fischer (wikipedia)
Distributed discrete log algorithm (half page self-contained proof): Breaking the Circuit Size Barrier for Secure Computation Under DDH, Boyle, Gilboa, Ishai Section 3.1.
Complexity classes, Chernoff bound and amplification.
Tutorial notes: tutorial3.pdf
Homework 1 hw1.pdf, by April 10
Second tutorial notes: tutorial2.pdf
First tutorial notes: tutorial1.pdf
We start next week (most probably).
To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed. The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.