cs579 COMPUTATIONAL COMPLEXITY (FALL 2023)

Computational complexity is the study of the limits of efficient computation. This graduate course will cover many of the most prominent algorithmic resources (time, space, non-determinism, randomness, interaction, quantum, etc.), and seek to understand why tasks can require large amounts of these resources. Further, these resources will be compared in their computational strength. In many cases (such as the P versus NP problem), answering these questions unconditionally is difficult, so this course will explore the known theory (completeness and reductions, oracle results, polynomial hierarchy assumptions) underlying current understanding.

**Lecture:** TR15:30-16:45, Siebel 1302.

**Staff:**

role | name | (netid) |
office hour |
---|---|---|---|

instructor: |
Prof. Michael A. Forbes | (miforbes) |
T17 (or by appointment), Siebel 3220 |

teaching assistant: |
Zander Kelley | (awk2) |
W10:30-12:30, Siebel 3303 |

The **calendar** lists lecture topics, associated lecture materials, and auxiliary reading. It also lists the problem sets with release- and due-dates.

The forum for the class is Piazza (code).

The submission server for the class is Gradescope (code). When submitting assignments, student must use their `@illinois.edu` netid so the course staff can appropriately map students to submissions.

A students grade in the course compromises of:

*psets*(70%): there are 6 biweekly psets of ~5 problems each. Each problem is worth 10 points. Problem sets later in the course will be lighter to allow time for the project. Problem sets will include the full text of each question, but may also include numbering to reference the question's origin.*project*(30%): see below for a description of the project

The lectures for the course will be in-person, except on rare occasions when announced otherwise.

Materials from lecture (boardwork, etc) will be posted, generally within 24 hours of the lecture, on the calendar.

Lectures will not be recorded, but recordings from previous versions of this course will be made available on the calendar. As this recordings are from the past, there may be some differences with the in-person lecture.

The main materials for the class are the above-mentioned lecture materials. Auxiliary pointers to written material will be listed for each lecture, and are approved materials for collaboration purposes.

Additional approved textbooks are as follows.

__Introduction to the Theory of Computation, by Sipser__: The first half of the course will roughly follow this book. Both the second- and third-edition of this textbook suffice for the course, but all numbering will refer to the second-edition.__Computational Complexity: A Modern Approach, by Arora and Barak__: The second half of the course will roughly follow this book. Drafts of the book are available online.

Familiarity with discrete mathematics (cs173), models of computation (cs374, cs475), algorithms (cs473); as well as mathematical maturity.

The course will use Piazza as a forum.

The forum will be the sole source of announcements from the course staff. Students should sign-up promptly to avoid missing such announcements.

The forum is also intended for students to connect amongst themselves on all course-related issues, **except** when such discussion reveals significant information about solutions to pending assignments. Posts can be made anonymously to other students (but not to the course staff). The students in the course can sometimes offer the best help; please make this resource the best it can be.

The forum is finally meant for private communication between the students and the course staff, especially for logistical matters such as scheduling conflicts. Emailing course staff directly is *heavily discouraged*. While the forum can be used for private help from the course staff on course content, a quicker and more thorough response is often achieved through a public discussion.

In order to avoid distracting other students, any student (without prior accommodation) who uses a computing device with a screen that does not lie flat on table/lap *must* sit in the back half of the lecture hall. Some examples:

- If you are using a tablet to take notes and the tablet lies flat on a table, you can sit wherever you want.
- If you are using a laptop, you must sit in the back half of the room.
- If you are using a smartphone and you leave it
*on the desk*, you can sit wherever you want. But if you use your smartphone and it does not lie flat, you must sit in the back of the room.

If you require an accommodation with regards to this policy, please contact the course staff.

Coursework must be submitted individually. However, verbal discussion (oral or electronic) with other students in the course is highly encouraged, subject to the constraint that submitted psets must list all such collaborators. However, the composition of the pset submissions must be solely the work of the listed author. In particular, no sharing of written solutions is allowed.

Students are allowed to use any listed course materials, or discussions with students or staff affiliated with the course. Students are forbidden from using any other online, textbook, or human resource.

The first violation of academic integrity is a zero for the entire assignment. The second violation is a reduction of 1 letter grade.

A students grade in the course compromises the 6 psets of 4 problems each. All problems from problem sets are worth the same number of points.

Regrade requests will be open for two weeks after an assignment is returned. Regrade requests will result in the *entire* assignment in being regraded; as a result the overall score may decrease.

Sample solutions will be distributed to students when the problem sets are returned (please keep the internet free of easily-found solutions!). These sample solutions will be selected from student submissions (with names omitted). Please inform the course staff if you wish to * opt-out* of ever being selected.

Students are highly encouraged to turn-in assignments on-time to avoid falling behind on the material, and to incentivize this any late problem sets will automatically lose 10% in value. However, to be flexible, for each pset students can automatically take (without asking) a 3-day extension (72 hours). The extension (and resulting penalty) applies to the *entire* problem set, regardless of whether a partial submission was made on time. Problem sets will not be accepted past this 3-day extension window.

Note that based on historical grade data, if a student submitted *all* problem sets late then the 10% penalty would likely result in a drop of 1 letter grade.

Figures are **highly** encouraged. Many algorithms act on combinatorial objects such as graphs, and discussing such objects without a figure is a pain to write, and to read.

To use your time wisely, students are encouraged to focus on *content* of their coursework over *format*. However, content and format are not fully independent. As such, students are suggested to consider the following advice on submission formats.

**typesetting submissions:**Typesetting is generally encouraged. Electronic documents are easier to revise, and as such easier to use to ensure content quality as first drafts are rarely polished. Typesetting ensures legibility, which is important as the course staff cannot give credit for work they cannot read. Finally, learning to typeset is a skill useful in many parts of academia and industry.**However**, including figures in typeset documents is often difficult, to the point that often students prefer to omit figures altogether. This can lead to a significant decrease in coursework clarity and concision, which can impact the score received. For beginners to typesetting there is the additional burden of having to learn to typeset while learning the course material. The result is often an ungainly document, to the point that the legibility gained by typesetting is offset by the poor usage of typesetting's abilities.**handwriten submissions:**Handwritten submissions are accepted, as long as they are at least as legible as the handwriting of the instructor, and also that the submissions use**figures**.

There is a project for this course. In groups of 2 (possibly 3, depending on rounding), students will explore an additional topic in computational complexity. (Students can request to be assigned a random group by asking the course staff.) Midway through the semester a list of notable papers will be released, and the student groups will choose (with consultation of the professor) one of (or possible a pair of) these papers to understand. More experienced students are expected to choose more advanced topics.

In the last week of class students will make a 30-minute presentation on their topic, and will also write a short (>= 6 pages, with reasonable fonts/margins) report (due on the last day of the semester). The presentation and report must answer the following questions:

- what is the problem the paper(s) are trying to solve?
- why is this problem interesting?
- what is the prior work on this problem? (at the time of writing of the paper(s))

- what were the main
*ideas*used in the paper(s)? - what are
*some*of the technical details?

The presentation should be split between background and results, while the report should be one-third background and two-thirds results. Students are *required* to attend at least one project presentation other than their own.