Syllabus
- Examples of randomized algorithms and protocols
- Classes of languages defined by randomized algorithms and their relations
- Minimax theorems (von Neumann, Yao)
- Methods of derandomization: pairwise independent variables, expanders
- Markov chains and their applications: random walks and connectivity, satisfiability algorithms, approximate counting (satisfying assignments, matchings in dense graphs), coupling (counting of graph colorings)
- Introduction into queuing theory
- Streaming algorithms
- Randomized protocols and verification: linearity testing, PCP theorem (the proof of the exponential version)
Annotation
The course covers the use of randomness in design of efficient algorithms. Use of randomness allows to solve problems more efficiently or even to solve problems that are otherwise intractable. The course covers techniques for design of randomized algorithm, demonstrated on concrete problems. We assume knowledge on the level of the courses NDMI084 Introduction to approximation and randomized algorithms and NTIN022 Probabilistic
Techniques.