Overview

Class Meetings: MW 12:30pm–1:45pm, Walsh, Room 396

Office Hours:      M 2:00pm–3:00pm, St. Mary's Hall, Room 354

Instructor: Sasha Golovnev

Email: alexgolovnev+gems@gmail.com

Description:

How do you send a letter to a stranger that only she can read? How can you prove that you located a picture of Waldo in a complex image without revealing any information about his position? How do you match students with schools (and win the Nobel prize for doing so)? What can a computer learn, and what can a computer never solve? We will answer these and many other questions by using wonderful ideas from Theoretical Computer Science.

Prerequisites:

Familiarity with mathematical proofs, discrete mathematics, linear algebra, and basic algorithms.

Course questionnaire:

Please complete this form by Sunday, August 28.

Textbook:

Although there's no textbook for this course, we will post references for each lecture.

Grading:

Grading will be based on five or six homework problem sets.

Canvas page:

https://georgetown.instructure.com/courses/152656.

Tentative Schedule

Class Date Topic Slides References
Part I. Algorithms
1 8/24 Easy and Hard Problems Slides Greedy: [Eri19, Sec 4.2]; TSP: [MCPZ]; SAT: [wiki].
2 8/29 Approximation Algorithms Slides Vertex Cover: [War05, Sec 1]; TSP: [Cow02].
Homework 1
3 8/31 Randomized Algorithms Slides Cloud Sync: [Kan07, Sec 1]; Max-CUT: [Har14].
4 9/6 Data Structures Slides Function Inversion: [CK19, Appendix C]; Bloom Filters: [Wag03].
5 9/7 Streaming Algorithms Slides Missing Elements: [Mut05, Sec 1.1]; Majority: [wiki]; Approximate Counting: [And17].
6 9/12 Exponential-time Algorithms Slides TSP: [Tre19, Sec 2]; 3-SAT: [Nii11, Sec 2].
7 9/14 Fine-grained Complexity Slides OV: [Bri19, Sec 4]; k-DS: [VW20, Sec 4.1].
8 9/19 Graph Colorings Slides Exact Col: [Hus15, Alg D]; Exact 3-Col: [Hus15, Alg P]; Approx 3-Col: [Hus15, Alg W].
Homework 2
9 9/21 Heuristic Algorithms Slides TSP: [JM95, Sec 2], [Nil03]; SAT: [Rij19], [GKSS08].
10 9/26 Linear Programming Slides LP: [Gri14, Chap 2], [Eri18].
11 9/28 Integer Linear Programming Slides ILP: [Tay19]; Examples: [mip]; ILP: [CTS95].
12 10/3 Stable Matchings (by Karthik Gajulapalli) Slides Gale-Shapley: [Eri19, Sec 4.5]; Stable Matchings: [EIV].
Homework 3
Part II. Complexity Theory
13 10/5 Undecidability Slides Undecidability: [Ste12], [Eri18, Sec 7].
14 10/12 Gödel's Incompleteness Slides Incompleteness: [Ste12].
15 10/17 P vs NP Slides NP-complete problems: [DPV08].
16 10/19 Circuit Complexity Slides Circuits: [AB07, Sec 6.0, 6.3, 6.4].
17 10/24 Circuit Complexity II Slides Symmetric Functions, TH2: [Kul18, Sec III]; Lower Bound: [Weg87, Theorem 2.1].
18 10/26 Error Correcting Codes Slides Hat Game: [Ber01, pp 4-6]; Ulam's game: [Kir19].
Homework 4
19 10/31 Randomness Slides Probabilistic Complexity Classes: [Tre02, Sec 5].
20 11/2 Communication Complexity Slides Communication: [AB07, Sec 12-12.2.1]; VLSI: [Lov89, Sec 1].
Part III. Cryptography
21 11/7 Secret Key Cryptography Slides OTP: [BS20, Sec 2.1]; Stream Ciphers:[BS20, Sec 3.1-3.3].
22 11/9 Modular Arithmetic - Primes: [Bon03]; Composites: [Bon03].
23 11/14 Public Key Cryptography Slides RSA: [BS20, Sec 10.3]; Attacks:[Bon99], [HDWH12].
Homework 5
24 11/16 Secret Sharing Slides Secret Sharing: [BS20, Sec 11.6.1]; Example: [wiki].
25 11/21 Levin's Universal OWF, Impagliazzo's Five Worlds - Levin's OWF: [Pas09, Sec 1]; Impagliazzo's worlds: [Imp95].
Part IV. Learning
26 11/28 PAC Learning - PAC: [Kli05].
27 11/30 VC Dimension - VC: [Sha08].
28 12/5 Linear Regression - Gradient Descent: [Gro20].

Course Policies

Academic Honesty:

We encourage you to discuss the homework assignments with your classmates, however you must explicitly list all collaborators and materials that you used, and you must write up your own solution to every problem. See Georgetown University Honor System. When in doubt, ask the instructor what is allowed.

Late Submissions:

Late submissions of homework solutions are graded with a 10% penalty per day of late submission.

Disability Disclosure Statement:

If you have a disability that may affect your academic work or well-being and for which accommodations may be necessary, please inform us and contact the Academic Resource Center.

Title IX:

We are committed to supporting survivors and those impacted by sexual misconduct. For details of University resources, consult Georgetown University Sexual Misconduct Reference Guide.

Religious Observance:

Any student who is unable to attend a class because of the observance of a major religious holiday will be provided with the opportunity to make up for the class.