Randomness and Computation, Spring 2022

In this course we will see various aspects and applications of probability theory in theoretical computer science.

We start with a few lectures on the iconic probabilistic method. Originally developed by Paul Erdős, this powerful method is used to prove the existence of certain desired objects using probabilistic arguments.

We will then see random walk arguments in satisfiability algorithms and in error reduction of randomized algorithms using expander graphs.

Then we will visit interactive proof systems and an overview of the famous PCP theorem which is used in proving hardness of approximation.

Finally we will see derandomization which makes certain probabilistic arguments deterministic. We will also see one-way functions and pseudorandomness, the area which is about constructing deterministic objects which look random to various observers.

Instructor

• Navid Talebanfard

Lectures

• Feb 17: union bound, lower bound for Ramsey numbers, tournaments, dominating sets, [AS], ch.1. Homework 1
• Feb 24: linearity of expectation, alteration, solution to homework 1, improved bound for Ramsey numbers, independent set in graphs, [AS], ch. 2,3.
• Mar 3: Sperner's theorem, Lovász Local Lemma, [AS], ch.5. Homework 2
• Mar 10: Inequalities: Markov, Chebyshev, Chernoff. Erdős distinct sums problem.
• Mar 17: Markov chains, 2-SAT algorithm, coupling arguments, intro to 3-SAT algorithm, [MU], ch.7.
• Mar 24: Schöning's algorithm, intro to graph random walks, s-t connectivity
• Mar 31: Expander walks, error reduction. [J], ch. 15, 23.
• Apr 7: Interactive proof systems, Graph Non-Isomorphism, Pairwise independent hash functions, [AB], ch.8.
• Apr 14: Graph Non-Isomorphism, Set lower bound. 3-TAUT in IP, Sum-check protocol.
• Apr 21: Hardness of approximation, Introduction to PCP theorem. [AB], ch. 11.
• Apr 28: PCP continued, Walsh-Hadamard codes.
• May 5: Exponential size PCPs.
• May 12: Cryptography, encoding schemes, one-way functions. [AB], ch. 9.
• May 19: Pseudo-random generators, unpredictability, hybrid argument.

Literature

• [MU] Mitzenmacher and Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis.
• [AS] Alon and Spencer, The Probabilistic Method.
• [AB] Arora and Barak, Computational Complexity, A Modern Approach.
• [J] Jukna, Extremal Combinatorics, 2nd Edition.

Grading

Homework contributes 49% and final exam contributes 51% of the whole grade.

When and where

Thursdays 14-16:20 in K5, Karlín building.

Contact info

Queries about the course should be sent to talebanfard@math.cas.cz