cs579: COMPUTATIONAL COMPLEXITY (SPRING 2020)

ANNOUNCEMENTS

  • none yet ...

ABOUT

Class: TR3:30-4:45 Siebel 1109

Professor: Prof. Michael A. Forbes (miforbes)
Teaching Assistant: Minghao Liu (ml58)

Office Hours:

miforbes: T5 (or by appointment), at Siebel 3220
Minghao: W3-5, Siebel 3303

Piazza: https://www.piazza.com/illinois/spring2020/cs579 (access code given in lecture)

Schedule: lists lecture topics, with links to lecture notes, pset release/due dates, and suggested reading.

DESCRIPTION

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.

Prerequisites: familiarity with algorithms, models of computation, and discrete mathematics; as well as mathematical maturity

REFERENCES

The first half of the course will roughly follow the treatment given in Introduction to the Theory of Computation, by Sipser. Both the second- and third-edition of this textbook suffice for the course, but all numbering will refer to the second-edition.

The second half of the course will roughly follow the treatment given in Computational Complexity: A Modern Approach, by Arora and Barak. Drafts of the book are available online.

The schedule contains for each lecture the associated suggested reading, as well as scanned (handwritten) lecture notes.

PIAZZA

The class has a Piazza page, which will serve two purposes. The first is for course announcements, which will also be posted on this website. The second is to host a discussion forum where students can ask questions of their co-students as well as the course staff. Such discussion is highly encouraged, subject to the below collaboration policy on homework. Please sign-up!

LAPTOPS

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 instructors.

GRADING

Grades will be 70% problem sets and 30% for the project.

PROBLEM SETS:

There will be 6 biweekly problem sets of ~5 problems each, where 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.

Submission Policy: Problem sets will be posted by 2pm on the day of release, and are due 2pm on the due date. An electronic (pdf) copy must be submitted by email to the course staff (miforbes and ml58). Each problem should be on a separate page. The subject line of the email should be "[cs579] psetN submission" (N = pset number) and the filename must be "psetN_NETID.pdf" (N = pset number, NETID = your netid).

Collaboration Policy: Students are forbidden from directly searching for solutions on the internet, but may consult the exercise-hints in the textbooks for the course. That said, students are highly encouraged to collaborate in small groups. However, this must be a two-way collaboration. Students should not dictate complete solutions to other students, either verbally or written. Solutions must be written independently regardless of collaboration, and psets must list the collaborators you worked with.

Late Policy: 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.

Solutions: Hard-copy 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.

PROJECT:

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 class). The presentation and report must answer the following questions:

background:
  • 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))
results
  • 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.