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

11:00-12:15 TTh Room E203 CB

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.
In the low-likelihood event that everything goes smoothly and I have some time to spare, I would like to cover Chapter 11 on the PCP Theorem.

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.
Late submissions will not be accepted and in general you will be better off turning in what you have on time rather than seeking extra time to complete your work. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations".

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