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

Part I. Algorithms | ||||

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

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

Homework 1 | ||||

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

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

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

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

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

Homework 2 | ||||

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

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

10 | 9/25 | Linear Programming | Slides | LP: [Gri14, Chap 2], [Eri18]. |

11 | 9/27 | Integer Linear Programming | Slides | ILP: [Tay19]; Examples: [mip]; ILP: [CTS95]. |

12 | 10/2 | Stable Matchings (by Karthik Gajulapalli) | Slides | Gale-Shapley: [Eri19, Sec 4.5]; Stable Matchings: [EIV]. |

Homework 3 | ||||

Part II. Complexity Theory | ||||

13 | 10/4 | Undecidability | Slides | Undecidability: [Ste12], [Eri18, Sec 7]. |

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

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

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

17 | 10/23 | Circuit Complexity | Slides | Circuits: [AB07, Sec 6.0, 6.3, 6.4]. |

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

19 | 10/30 | Randomness (by Karthik Gajulapalli) | Slides | Sampling: [Tar09, Sec 2]; Amplification: [Sud07, Sec 1--3]. |

Homework 4 | ||||

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

Part III. Cryptography | ||||

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

22 | 11/8 | Modular Arithmetic | - | Primes: [Bon03]; Composites: [Bon03]. |

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

24 | 11/15 | Secret Sharing | Slides | Secret Sharing: [BS20, Sec 22.1]; Example: [wiki]. |

Homework 5 | ||||

25 | 11/20 | Impagliazzo's Five Worlds (by Karthik Gajulapalli) | Slides | Impagliazzo's worlds: [Imp95]. |

Part IV. Learning | ||||

26 | 11/27 | PAC Learning | - | PAC: [Kli05]. |

27 | 11/29 | VC Dimension | - | VC: [Sha08]. |

28 | 12/4 | Linear Regression | - | Gradient Descent: [Gro20]. |