cs579: COMPUTATIONAL COMPLEXITY (SPRING 2018)

ANNOUNCEMENTS

  • 2018-04-11: Class on 2018-04-16 has been canceled, as miforbes will be away.
  • 2018-03-28: Robert's office hours have been updated.
  • 2018-03-26: the project topics have been posted.
  • 2018-02-17: lecture 8,9 notes have been posted.
  • 2018-02-17: additional hints have been added to pset2.
  • 2018-02-10: lecture notes have been posted, and the schedule has been updated by being pushed back by 1 lecture.
  • 2018-02-10: pset2, #1(a) has been updated to reflect that the reduction should run in the logarithm of s(n) space.
  • 2018-01-24: miforbes is away next week. Instead, Robert will be lecturing, and he will have 2 additional office hours (Tues 2pm, Thurs 1pm).
  • 2018-01-24: Corrected typo in the definition of L' in problem 4 of pset 1.
  • 2018-01-21: Updated the syllabus to clarify that exercise-hints from Arora-Barak may be consulted.

ABOUT

Class: MW3:30-4:45 SC 1105

Professor: Prof. Michael A. Forbes (miforbes)
Teaching Assistant: Robert Andrews (rgandre2)

Office Hours:

miforbes: M2, W1 (or by appointment), at Siebel 3220
Robert: F2-4 F10:30-12:15, lounge area between Siebel 3304 and 3232

Piazza: http://www.piazza.com/illinois/spring2018/cs579

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

Much of the class will roughly follow the treatment given in Computational Complexity: A Modern Approach, by Arora and Barak. Drafts of the book are available online, and the full book can be accessed when on-campus. Reference chapters for each lecture will be posted on the schedule, but the details will sometimes differ.

Scanned (handwritten) lecture notes will be posted on the schedule.

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!

GRADING

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

PROBLEM SETS:

There will be 6 biweekly problem sets of ~4 problems each, where each problem is worth 10 points. Problem sets later in the course will be lighter to allow time for the project.

Submission Policy: Problem sets will be posted by 3:30pm on the day of release, and are due 3:30pm on the due date. An electronic (pdf) copy must be submitted by email to the course staff (miforbes and rgandre2). Each problem should be on a separate page. The subject line of the email should be "[cs579] psN submission" (N = pset number) and the filename must be "NETID_psN.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 Arora-Barak. 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 homework will automatically lose 10%. However, to be flexible, students have a total of 6 late days (24 hours each, rounded up to an integral number of days), no more than 3 of which can be used for any particular homework. Problem sets will not be accepted for credit once the late days are exhausted.

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.