22C:131 (CS: 3310) Limits of Computation

Instructor: Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: M 11:30-1:00, W 1:00-2:30 and by appointment.

This course is a mathematical exploration of the limits of the power of computers. Some of the questions we ask and attempt to answer are the following. Are there problems that cannot be solved on any computer? How does one determine if a given problem can or cannot be computationally solved? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and which problems cannot be solved on a computer? How does the power of a computer change, if it has access to random bits? What happens when we relax the notion of solving a problem to "approximately" solving a problem - does this fundamentally change which problems can and which problems cannot be solved on a computer?

In attempting to answer these questions we will study models of computation such as Turing machines and Boolean circuits, time complexity classes such as P, NP, NP-complete, space complexity classes such as PSPACE, L and NL, and randomized complexity classes such as RP and BPP. We will also study interactive proofs and the corresponding complexity class IP and the surprising result that IP = PSPACE. Time permitting, we will also study the PCP theorem and hardness of approximation.

Prerequisite
Undergraduate Algorithms (22C:31) or its equivalent.

Textbook
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4.

Since I don't consider myself an expert in complexity theory, I'll stick pretty closely to the textbook. This will not a problem because the book is beautifully written and conveys the excitement of current research in complexity theory. The book was published in 2009 and covers several recent (post-2000) results especially in the later chapters. While we will not get to most of these in class, I hope that some of you will be inspired enough by what we cover in class to read on your own some of the later chapters, e.g., on quantum computing, communication complexity, complexity of counting, etc.

List of Topics
I anticipate covering the first 8 chapters of the Arora-Barak book. So the list of topics is:

• Turing machines, uncomputability.
• The classes P, NP and NP-completeness.
• Diagonalization and time hierarchy theorems.
• Space complexity.
• Polynomial hierarchy.
• Boolean circuit complexity.
• Randomized complexity classes.
• Interactive proofs.

Grading
Plus/Minus grading will be used for the course. There are two components that will determine your grade.

• Homeworks: 50% 5-6 homeworks will be assigned during the semester. These will be posted on the class homepage and you will have two weeks for each homework.

• 2 Exams: 50% There will be one mid-term exam (worth 20% of your grade) and one final (worth 30% of your grade). The current plan is to have the midterm on October 4th, Thursday. For the midterm, I would like to find a 2 hour slot on October 4th (possibly in the evening) that works for everyone. All exams will be open book/notes exams. The final will be cumulative; time and location of the final will be announced in mid-September.

Solutions will be provided for all graded work.

I have no expectations with regards to attendance or class participation for this course. However, if you do come to class, I would like you to show up on time. The homeworks will mostly be proof-based and you will have to spend time not only figuring out the proof, but also how to present it clearly.

Teaching Assistant Information
I do not yet know if we will have a TA for the course. If the course does get assigned a TA, I'll announce the TA's co-ordinates on the course page.

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about how the course is being conducted by me or by the TA (if we have one) please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Alberto Segre(alberto-segre@uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on student rights and responsibilities for more information.

Administrative Home
This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Electronic Comminication
University policy specifies that students are responsible for all official correspondences sent to their University of Iowa e-mail address (@uiowa.edu). Faculty and students should use this account for correspondence.

CLAS Final Examination Policies
The final examination schedule for each class is announced around the fifth week of the semester by the Registrar. Final exams are offered only during the official final examination period. No exams of any kind are allowed during the last week of classes. All students should plan on being at the UI through the final examination period. Once the Registrar has announced the dates and times of each final exam, the complete schedule will be published on the Registrar's web site.

Understanding Sexual Harassment
Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI Comprehensive Guide on Sexual Harassment for assistance, definitions, and the full University policy.

Reacting Safely to Severe Weather
In severe weather, class members should seek appropriate shelter immediately, leaving the classroom if necessary. The class will continue if possible when the event is over. For more information on Hawk Alert and the siren warning system, visit the Department of Public Safety website.