Syllabus

Course Description

In this course, we explore the power and limitations of efficient computation. We compare basic models of computations such as Turing Machines (deterministic and nondeterministic) and boolean circuits. The course illustrates the notion of computational intractability (P vs. NP) through the lens NP-completeness. We also explore the power of randomness (P vs. BPP) and interaction (IP vs. PSPACE) in computation, along with some modern topics in the theory of computing (e.g., fine-grained complexity).

Prerequisites

The direct prerequisite for this course is CS 4820. We will also assume that everyone is familiar with the material in CS 2110, CS 3110, and CS 2800 — direct and indirect prerequisites of CS 4820. Concretely, you should remember your basic algorithms (e.g., dynamic programming and network flow), basic computability (e.g., Turing machines and undecidability of the halting problem), and basic NP-completeness. We expect everyone to be comfortable reading and writing mathematical proofs at the level of CS 4820.

Course Material

The main textbook for the course is Computational Complexity: A Modern Approach by Arora-Barak. Additionally, some readings may be suggested from Introduction to the Theory of Computation by Sipser.
Both books should be available at the Cornell Store and on CAMP.

Grades

Your grade will based on homework, in-class quizzes, a final project, and participation.

• Homework: 40%
  Homework will be assigned ~every 2 weeks on Canvas.
• Quizzes: 40%
  Quizzes will happen ~weekly during lecture on Thurs. The lowest 3 scores will be dropped, so no make-ups will be offered.
• Project: 15%
  The final project will be discussed in class with instructions posted to Canvas.
• Participation: 5%
  Evaluated based on lecture/OH participation, extra credit on homework assignments, and completion of course evaluations.

CS 5814

CS 5814 co-meets with CS 4814. The course material of the two classes is the same, but across various assignments and the final project, there will be additional work / higher expectations for students enrolled in the graduate offering. These expectations will be communicated on each assignment.

Communication and Discussion

Ed Discussions allows for open discussions of all course-related questions. You are encouraged to post any questions you might have about the course material. If discussing a homework question, be mindful not to post significant aspects of your solution. Ed is the most effective way to communicate with course staff. Please avoid email if Ed will do. Each staff member also holds Office Hours, where you can stop by to get help on homework or simply discuss the course material. We look forward to seeing you at OH!

Academic Integrity

In CS 4814, you are expected to uphold Cornell's Code of Academic Integrity:

Absolute integrity is expected of every Cornell student in all academic undertakings. Integrity entails a firm adherence to a set of values, and the values most essential to an academic community are grounded on the concept of honesty with respect to the intellectual efforts of oneself and others. Academic integrity is expected not only in formal coursework situations, but in all University relationships and interactions connected to the educational process, including the use of University resources. […]

A Cornell student's submission of work for academic credit indicates that the work is the student's own. All outside assistance should be acknowledged, and the student's academic position truthfully reported at all times. In addition, Cornell students have a right to expect academic integrity from each of their peers.

SDS Accommodations

This course complies with the Cornell University policy and equal access laws to ensure that students with disabilities can access the same academic experience as their peers in this course. Requests for academic accommodations should be made during the first week of the semester. Students must register with Student Disability Services (SDS) to provide appropriate accommodations. Forward your SDS letter (via email) to the professor. The Course Staff will then be in touch about how we can accommodate you.

Inclusion

We are committed to making CS 4814 an inclusive learning environment, where every student can learn the material and enjoy the class. You deserve to be treated with respect, by your classmates and the course staff. In turn, we expect students to communicate in a respectful manner with the instructors, course staff, and fellow students. If you experience anything in CS 4814 that goes against these values, please contact the instructors, so that the course staff can address the issue.