Class | Date | Topic | Slides | References |
---|---|---|---|---|

Part I. Algorithms | ||||

1 | 1/26 | Easy and Hard Problems | Slides | Greedy: [Eri19, Sec 4.2]; TSP: [MCPZ]; SAT: [wiki]. |

2 | 1/28 | Approximation Algorithms | Slides | Vertex Cover: [War05, Sec 1]; TSP: [Cow02]. |

Homework 1 | ||||

3 | 2/2 | Randomized Algorithms | Slides | Cloud Sync: [Kan07, Sec 1]; Max-CUT: [Har14]. |

4 | 2/4 | Streaming Algorithms | Slides | Missing Elements: [Mut05, Sec 1.1] Majority: [wiki]; Approximate Counting: [And17]. |

5 | 2/9 | Data Structures | Slides | Function Inversion: [CK19, Appendix C]; Bloom Filters: [Wag03]. |

6 | 2/11 | Exponential-time Algorithms | Slides | TSP: [Tre19, Sec 2]; 3-SAT: [Nii11, Sec 2]. |

Homework 2 | ||||

7 | 2/16 | Fine-grained Complexity | Slides | OV: [Bri19, Sec 4]; k-DS: [VW20, Sec 4.1]. |

8 | 2/18 | Graph Colorings | Slides | Exact Col: [Hus15, Alg D]; Exact 3-Col: [Hus15, Alg P]; Approx 3-Col: [Hus15, Alg W]. |

9 | 2/23 | Linear Programming | Slides | LP: [Gri14, Chap 2]. |

10 | 2/25 | Heuristic Algorithms | Slides | TSP: [JM95, Sec 2], [Nil03]; SAT: [Rij19], [GKSS08]. |

11 | 3/2 | Distributed Algorithms by Nitin Vaidya | Slides | |

12 | 3/4 | Integer Linear Programming | Slides | ILP: [Tay19]; Examples: [mip] |

Homework 3 | ||||

Part II. Complexity Theory | ||||

13 | 3/9 | Undecidability | Slides | Undecidability: [Ste12], [Eri18, Sec 7]. |

14 | 3/11 | Gödel's Incompleteness | Slides | Incompleteness: [Ste12]. |

15 | 3/16 | P vs NP | Slides | NP-complete problems: [DPV08]. |

16 | 3/18 | Circuit Complexity | Slides | Circuits: [AB07, Sec 6.0, 6.3, 6.4]. |

17 | 3/23 | Circuit Complexity II | Slides | Symmetric Functions, TH_{2}: [Kul18, Sec III]; Lower Bound: [Weg87, Theorem 2.1]. |

18 | 3/25 | Randomness | Slides | Probabilistic Complexity Classes: [Tre02, Sec 1, 2]. |

Homework 4 | ||||

19 | 4/6 | Error Correcting Codes | Slides | Hat Game: [Ber01, pp 4-6]; Ulam's game: [Kir19]. |

20 | 4/8 | Communication Complexity | Slides | Communication: [AB07, Sec 12-12.2.1]; VLSI: [Lov89, Sec 1]. |

Part III. Cryptography | ||||

21 | 4/13 | Secret Key Cryptography | Slides | OTP: [BS20, Sec 2.1]; Stream Ciphers:[BS20, Sec 3.1-3.3]. |

22 | 4/15 | Modular Arithmetic | Slides | Primes: [Bon03]; Composites: [Bon03]. |

23 | 4/20 | Public Key Cryptography | Slides | RSA: [BS20, Sec 10.3]; Attacks:[Bon99], [HDWH12]. |

Homework 5 | ||||

24 | 4/22 | Secret Sharing | Slides | Secret Sharing: [BS20, Sec 11.6.1]; Example: [wiki]. |

25 | 4/27 | Levin's Universal OWF, Impagliazzo's Five Worlds | Slides | Levin's OWF: [Pas09, Sec 1]; Impagliazzo's worlds: [Imp95]. |

Part IV. Learning | ||||

26 | 4/29 | PAC Learning | Slides | PAC: [Kli05]. |

27 | 5/4 | VC Dimension | Slides | VC: [Sha08]. |

28 | 5/6 | Linear Regression | Slides | Gradient Descent: [Gro20]. |