ANNOUNCEMENTS
ABOUT
Class: TR3:30-4:45 SC 1109
Professor: Prof. Michael A. Forbes (miforbes)
Teaching Assistant: Zander Kelley (awk2)
Office Hours:
miforbes: T5, R1 (or by appointment), at Siebel 3220
Zander: W4-6, Siebel 3303
Piazza: https://www.piazza.com/illinois/spring2019/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
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!
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 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 awk2). 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 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 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: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.