PCP and inaproximability, notes tutorial13.pdf (the solutions contain literature for that)

Notes tutorial12.pdf

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.

3blue1brown blockchain (video on youtube)

a use of Merkle tree (video on youtube)

https://en.wikipedia.org/wiki/Merkle_tree

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).

See SIS:

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.

## Useful links

- Lecture page: prof. Jiří Sgall.
- Previous run of this tutorial (czech only).