# Karel Král

kralka (AT) iuuk.mff.cuni.cz

# NDMI025 - Randomized Algorithms

## What happened

### Jun 3

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

### May 27

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

### May 20

Hashing, uses etc tutorial11.pdf.

### May 13

Derandomization, Yao, hash functions tutorial10.pdf.

### May 6

Electrical networks theory tutorial9.pdf.

### Apr 29

Coupling again, intro to streaming algorithms.

Problems from tutorial8.pdf

Homework 2 hw2.pdf, by May 16

### Apr 22

Matchings, IP protocol for permanent.

Problems from tutorial7.pdf

### Apr 15

Counting, permanents and determinants, matchings.

Problems from tutorial6.pdf

### Apr 8

Equivalence of norms (inequalities with Euclidean and Manhattan norm), coupling lemma and mixing time on a hypercube.

Problems from tutorial5.pdf

### Apr 1

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.

### Mar 25

Complexity classes, Chernoff bound and amplification.

Tutorial notes: tutorial3.pdf

Homework 1 hw1.pdf, by April 10

### Mar 18

Second tutorial notes: tutorial2.pdf

### Mar 11

First tutorial notes: tutorial1.pdf

### Mar 4

We start next week (most probably).

## Credit requirements

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.