IST Austria Courses
IST Austria logo

Computer Science track core course

Instructors: Krishnendu Chatterjee, Vladimir Kolmogorov and Krzysztof Pietrzak

Teaching Assistants: Amir Goharshady, Michal Rolinek

 

 

 

 

 

Lectures

Date Topic Lecture Notes Homework
28-Feb-17 Probabilistic Complexity Classes CS Core Course 2016 HW 1
02-Mar-17 Polynomial Identity Testing and Branching Problems   HW 2
07-Mar-17 Decision Making under Uncertainty    
09-Mar-17 Randomized Weighted Majority   HW 3
14-Mar-17 Randomized Minimum Cut   HW 4 HW 5
23-Mar-17 Balls and Bins   HW 6
28-Mar-17 Chernoff Bound, Power of two choices    
30-Mar-17 The Probabilistic Method and LLL    
       
  Markov chains and mixing times. Background reading (optional): 1, 2, 3.    
2-May-17 Basics of Markov Chains   hw-mc-1
4-May-17 Coupling and Path Coupling    
9-May-17 Perfect sampling, Coupling from the past    
11-May-17 Mixing times via path congestion   hw-mc-2
       
1-June-17 LP duality, s-t minimum cut/maximum flow   hw-lp-1
6-June-17 Polytopes and integrality   hw-lp-2
8-June-17 Ellipsoid method    
13-June-17 SDP relaxations