Overview

Class Meetings: MW 9:30am–10:45pm, ICC, Room 103

Office Hours:      TBA

Office Hours:      TBA

TAs: Karthik Gajulapalli and Sam King

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.

Textbook:

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

Grading:

Grading will be based on five homework problem sets.

Canvas page:

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

Tentative Schedule

Class Date Topic Slides References
Part I. Algorithms
1 8/27 Easy and Hard Problems
2 9/2 Approximation Algorithms
3 9/3 Randomized Algorithms
4 9/8 Data Structures
5 9/10 Streaming Algorithms
6 9/15 Exponential-time Algorithms
7 9/17 Fine-grained Complexity
8 9/22 Graph Colorings
9 9/24 Heuristic Algorithms
10 9/29 Linear Programming
11 10/1 Integer Linear Programming
12 10/6 Stable Matchings
Part II. Complexity Theory
13 10/8 Undecidability
14 10/15 Gödel's Incompleteness
15 10/20 P vs NP
16 10/22 Error Correcting Codes
17 10/27 Circuit Complexity
18 10/29 Circuit Complexity II
19 11/3 Randomness
20 11/5 Communication Complexity
Part III. Cryptography
21 11/10 Secret Key Cryptography
22 11/12 Modular Arithmetic
23 11/17 Public Key Cryptography
24 11/19 Secret Sharing
25 11/24 Impagliazzo's Five Worlds
Part IV. Learning
26 12/1 PAC Learning
27 12/3 VC Dimension
28 12/8 Linear Regression

Course Policies

Academic Honesty:

We encourage you to discuss the homework assignments with your classmates in groups of no more than three people, 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.

No AI Tools Permitted:

The use of AI text generating tools at any point when working on the assignments will be treated as academic dishonesty.

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.