Overview

Class Meetings: TR 9:30am–10:45am

Office Hours:      T 10:45am–11:45am; W 4:00pm-5:00pm

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.

Videos:

Zoom information and videos will be posted on the Canvas page for this course.

Piazza:

Please sign up here.

Course questionnaire:

Please complete this form by Sunday, January 24.

Textbook:

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

Tentative Schedule

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

Grading:

Grading will be based on six homework problem sets.

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.