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 29.

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/132788.

Tentative Schedule

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].
5 9/8 Data Structures Slides Function Inversion: [CK19, Appendix C]; Bloom Filters: [Wag03].
4 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 - -
8 9/22 Graph Colorings - -
9 9/27 Linear Programming - -
10 9/29 Heuristic Algorithms - -
11 10/4 Distributed Algorithms - -
12 10/6 Integer Linear Programming - -
Part II. Complexity Theory
13 10/13 Undecidability - -
14 10/18 Gödel's Incompleteness - -
15 10/20 P vs NP - -
16 10/25 Circuit Complexity - -
17 10/27 Circuit Complexity II - -
18 11/1 Randomness - -
19 11/3 Error Correcting Codes - -
20 11/8 Communication Complexity - -
Part III. Cryptography
21 11/10 Secret Key Cryptography - -
22 11/15 Modular Arithmetic - -
23 11/17 Public Key Cryptography - -
24 11/22 Secret Sharing - -
25 11/24 Levin's Universal OWF, Impagliazzo's Five Worlds - -
Part IV. Learning
26 11/29 PAC Learning - -
27 12/1 VC Dimension - -
28 12/6 Linear Regression - -

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.