CSC 707 - Automata, Languages and Computability Theory (Spring 2024)

Course description

A basic question in computer science is to understand what tasks can be computed efficiently. For example, can we compute a task (e.g. factoring an integer) using limited resources (e.g. in polynomial time)?

Computational complexity studies the power and limitations of computation given bounded resources such as time, space, randomness, communication, parallelism, and their trade-offs. For example, is verifying a solution/proof as hard as finding one (non-determinism vs. determinism)? When is randomness necessary (randomness vs. determinism)? Can sequential computation be made parallel?

This course will explore these questions by studying various concrete computational models such as Turing machines, Boolean circuits, and Interactions. We will cover several classic, surprising, and beautiful results and techniques in this area, and highlight how they brought new insights to other areas such as cryptography and optimization.

Prerequisites and Homework 0

This is a PhD-level course. While there is no hard prerequisite, to follow the class, you are expected to be familiar with topics covered in Discrete Math (CSC 226), Algorithms (CSC 316) and Automata theory (CSC 333). In particular, it is important to refresh your memory on the following concepts:

Big-O notation and basic analysis of algorithms.
Basic counting and graph theory.
Reading and writing proofs. As with every theory course, you will encounter many proofs in class and will be required to write proofs in homework and exam.
Basics of Turing Machines, decidability, non-determinism, NP-completeness.

You are encouraged to solve the optional Homework 0 before coming to class. We will discuss the solution in the first lecture.

Textbook

We will mainly follow the book [AB] "Computational complexity: a modern approach" by Arora and Barak (with a web addendum here), with some simpler arguments taken from other resources. It is available online here (via NCSU libraries). There is also a hardcopy at the Hunt Library. Additional reading material can be found in the Resources section.

Class Participation

Any of the following activities can be counted towards class participation:

Class attendance is expected but not mandatory.
Participation on Ed and Perusall. You are expected to read and comment on some short readings/questions posted on Perusall before coming to class. For example, you can
- point out anything you find particularly confusing or interesting
- summarize an argument according to your own understanding
- spell out a high-level argument in detail
- point out possible connections to other topics/areas
- suggest potential improvement/questions
You may choose to comment anonymously (to the class except me). These comments will help me better prepare the lectures.

Scribe and More

Each student will help prepare scribe notes for 2 lectures and address any questions related to them. These notes will be shared on Perusall as a resource for everyone in class to learn the material.

1. Scribe

You will scribe notes for 2 lectures using LaTex. (A signup sheet will be available after the first class.) One goal of these notes is to provide a concise and accessible exposition of the lecture content so that other students can refer to after the lectures. Another goal is to complete and clarify the hand-wavy/sketchy/confusing parts of the lectures. You are encouraged to use outside sources such as other lecture notes, surveys, and papers to make your notes accessible, but you should understand the material well enough to write down everything in your own words, as you will be asked to explain the material to other students later on. You should make use of office hours to discuss any questions you may have on the lecture when preparing your notes.

Your scribe notes should fit in 3-4 pages, and must not exceed 4 pages, in the template provided.
Turn in a draft of your scribe within 5 days after the lecture.
Turn in a final version of your note within 3 days after receiving feedback from me.

2. Answer questions related to the lecture on Perusall and Ed

To show your understanding of the 2 scribe notes you write, you will be asked (or tagged) to address any questions/comments posted by others on the related material (e.g. readings, scribe notes) on Perusall and Ed after the scribe notes are posted.

Homework and Exam

There will be 4-6 questions for each problem set. You have 3 weeks to complete each of them. You are required to typeset your solution using LaTeX. Overleaf is a popular online LaTeX editor.

Homework policy:

You are encouraged to discuss homework questions with others in the class, but only after spending some time (~20 mins) on each question on your own. You must write down your own solutions, without consulting others while you are writing them. If you are not sure about what a question is asking, you should ask on Ed immediately.

Each student has 8 late days for homework submission for the whole semester, of which you can use up to 5 days on any problem set. Each late day is exactly 24 hours and cannot be subdivided, that is, a 5-minute late is counted as 1 late day. No request is required for these 8 late days, but any extension request beyond them will be subject to Academic Absence Verification. When late days are used up and a problem set is submitted L days late, the grade for that problem set will be multiplied by 0.9^L. No problem set will be accepted after 10 days have elapsed from the initial due date.

Final exam policy:

You are not allowed to discuss the final exam with others and must work on the final exam on your own. There is no late day for final exam submission. Any extension request will be subject to Academic Absence Verification.

Regrade policy:

If you dispute the grade received for a problem set, you must submit, in writing through Gradescope, a detailed and clearly stated argument for what you believe is incorrect and why, within 7 days after the homework was returned to you.

Schedule

The following tentative schedule is subject to change according to the pace and interest of the class.

Number	Date	Topics
1	1/9	Logistics, Topics preview, HW0
2	1/11	Turing machines
3	1/16	P, NP, Reductions
4	1/18	Reductions
5	1/23	NP-Completeness
6	1/25	Circuit-SAT, Cook-Levin Theorem
7	1/30	Hierarchy theorems and Padding, Ladner's theorem
8	2/1	Polynomial Hierarchy
9	2/6	Oracles
10	2/8	Relativization Barrier: Baker-Gill-Solovay
11	2/15	Space complexity, NSPACE vs. DSPACE
12	2/20	TQBF and PSPACE-completeness
13	2/22	PSPACE-complete of TQBF and 2-player games
14	2/27	Logspace, reductions and completeness
15	2/29	Complement of NSPACE
16	3/5	Non-uniformity, Circuits
17	3/7	Karp-Lipton theorem, Ciruit lower bounds
18	3/19	Probability Basics
19	3/21	Randomized algorithms
20	3/26	Randomized complexity classes
21	3/28	More randomized complexity classes
22	4/2	Randomness vs. Non-uniformity, Randomness vs. PH
23	4/4	Interactive proofs
24	4/9	Arthur-Merlin protocols
25	4/11	Derandomization
26	4/16	IP vs. PSPACE
27	4/18	Sumcheck Protocol
28	4/23	Probabilistic Checkable Proofs and Hardness of approximation