Overview

Instructor: Sasha Golovnev

Class Meetings:      TuTh 9:30am–10:45am, ICC, Room 118

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

Email: alexgolovnev+complexity@gmail.com

Textbooks: Arora-Barak [AB], Sipser [Sip].

Tentative Schedule

Class Date Topic References
Algorithmic Thinking
1 1/8 Representations of Objects, Computational Problems. [AB, Sec 1.1], [Sip, Sec 0].
2 1/13 Turing Machines. [AB, Sec 1.2], [Sip, Sec 3.1].
3 1/15 Variants of Turing Machines, Simulations. [AB, Sec 1.2], [Sip, Sec 3.2, 7.1].
Homework 1
4 1/20 Universal Turing Machines, Undecidability. [AB, Sec 1.3-1.5], [Sip, Sec 4.2, 7.2].
5 1/22 Time Hierarchy Theorem. [AB, Sec 3.1], [Sip, Sec 9.1].
6 1/27 - -
7 1/29 Non-determinism and NP. [AB, Sec 2.1, 2.7], [Sip, Sec 7.3].
8 2/3 Reductions, Satisfiability. [AB, Sec 2.2, 2.3.1-2.3.3], [Sip, Sec 7.4].
9 2/5 The Cook-Levin Theorem (by Karthik Gajulapalli). [AB, Sec 2.3-2.4], [Sip, Sec 7.4].
10 2/10 Search-to-Decision, co-non-determinism. [AB, Sec 2.5-2.6].
11 2/12 Ladner's Theorem, Mahaney's Theorem. [AB, Sec 2.6, 3.4], [Gro16].
Homework 2
12 2/19 Space Complexity. [AB, Sec 4.1-4.2], [Sip, Sec 8.0].
13 2/24 Savitch's Theorem. [AB, Sec 4.1, 4.3.1], [Sip, Sec 8.1-8.2, 8.4].
14 2/26 NL-Completeness. [AB, Sec 4.4.0-4.4.1], [Sip, Sec 8.5].
15 3/10 Immerman–Szelepcsényi Theorem. [AB, Sec 4.4.2], [Sip, Sec 8.6].
16 3/12 - -
17 3/17 PSPACE-Completeness. [AB, Sec 4.3], [Sip, Sec 8.3].
Homework 3
18 3/19 RP and coRP. [AB, Sec 7.3-7.4], [Sip, Sec 10.2].
19 3/24
20 3/26
21 3/31
22 4/7
23 4/9
24 4/14
25 4/16
26 4/21
27 4/23
28 4/28

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 safe and hospitable environment for all members of the community. 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.