IST Austria Courses
IST Austria logo

Computer Science track core course

Instructor: Krishnendu Chatterjee, Vladimir Kolmogorov, Krzysztof Pietrzak

Teaching Assistant: Bernhard Kragl, Josef Tkadlec, Michal Rolinek

Description

 

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.


Schedule

Note: course schedule changed after the easter break!

Lectures:
    Mon 9:15-10:30 (Mondi 1, except June 6 Mondi 2)
    Wed 10:15-11:30 (Big Seminar Room Lab Building West)
Recitations:
    Wed 11:45-12:35 (Big Seminar Room Lab Building West)


Requirements/Exams

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.

 


Credits

 6 ECTS


Final Grade

 

 

Lectures

Date Topic Blackboard Homework
  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