-->

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

Part I. Algorithms | ||||

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

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

Homework 1 | ||||

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

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

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

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

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

Homework 2 | ||||

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

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

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

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

12 | 10/6 | Stable Matchings | - | Hall's Theorem: [Sar11]; Gale-Shapley: [Eri19, Sec 4.5]. |

Homework 3 | ||||

Part II. Complexity Theory | ||||

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

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

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

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

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

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

19 | 11/3 | Randomness | Slides | Probabilistic Complexity Classes: [Tre02, Sec 5]. |

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

Homework 4 | ||||

Part III. Cryptography | ||||

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

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

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

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

Homework 5 | ||||

25 | 11/24 | Levin's Universal OWF, Impagliazzo's Five Worlds | - | Levin's OWF: [Pas09, Sec 1]; Impagliazzo's worlds: [Imp95]. |

Part IV. Learning | ||||

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

27 | 12/1 | VC Dimension | Slides | VC: [Sha08]. |

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