Instructor: Krishnendu Chatterjee, Vladimir Kolmogorov, Krzysztof Pietrzak
Teaching Assistant: Bernhard Kragl, Josef Tkadlec, Michal Rolinek
The goal of the CS core course is to expose students to key ideas in computer science, covering randomized algorithms, parametrized algorithms, optimization algorithms, and topics in cryptography.
Note: course schedule changed after the easter break!
Mon 9:15-10:30 (Mondi 1, except June 6 Mondi 2)
Wed 10:15-11:30 (Big Seminar Room Lab Building West)
Wed 11:45-12:35 (Big Seminar Room Lab Building West)
In the first part of the course (taught by Krishnendu Chatterjee), students will be asked to take turns preparing "scribe notes". Each class, one student will be the designated "scribe", taking careful notes during class and writing them up in LaTeX.
We host the lecture notes on GitHub. Please sign up and write an email with your username to Bernhard Kragl to get write access.
The final lecture notes are available here.
|I. Randomization (KC)|
|Mon 29 Feb||Probabilistic Complexity Classes||[bb1]||[hw1]|
|Wed 02 Mar||Polynomial Identity Testing & Branching Programs||[bb2]||[hw2]|
|Mon 07 Mar||Decision Making Under Uncertainty||[bb3]||-|
|Wed 09 Mar||Randomized Weighted Majority & Zero Sum Games||[bb4]||[hw3] [project]|
|Mon 14 Mar||Balls and Bins & Probabilistic Inequalities||[bb5]||[hw4]|
|Wed 16 Mar||Chernoff Bound & The Power of Two Choices||[bb6]||[hw5]|
|Mon 04 Apr||Randomized Minimum Cut||[bb7]||[hw6]|
|Wed 06 Apr||The Probabilistic Method (Lovász Local Lemma)||[bb8]||-|
|II. TBD (KP)|
|Mon 11 Apr||Coding (Shannon bound, Reed-Solomon)|
|Wed 13 Apr||Multiparty Computation (GMW)|
|Mon 18 Apr||no class (road closed)|
|Wed 20 Apr||Multiparty Computation (Yao's garbled circut)|
|III. Markov chains and mixing times (VK)
Background reading (optional): 1, 2, 3.
|Mon 25 Apr||Basics of Markov Chains||hw-mc1|
|Wed 27 Apr||Coupling and Path Coupling||hw-mc2|
|Mon 2 May||Perfect sampling, Coupling from the past|
|IV. TBD (KP)|
|Wed 4 May||Parameterized Algoritms / Kernelization, Bounded-depth search trees|
|Mon 9 May||Mixing times via path congestion (VK)|
|Wed 11 May||no lecture|
|Mon 16 May||public holiday|
|Wed 18 May|
|Mon 23 May||Parameterized Algorithms / Color coding, Treewidth|
|Wed 25 May||Parameterized Complexity / Lower bounds||hw-fpt|
|V. TBD (VK)|
|Mon 30 May||LP duality, min-cut/max-flow||hw-lp1|
|Wed 1 Jun||Polytopes and integrality||hw-lp2|
|Mon 6 Jun||Ellipsoid method|
|Wed 8 Jun||no lecture|
|Mon 13 Jun||no lecture|
|Wed 15 Jun||SDP relaxations|