PCMI 2000 Click on the links below for course abstracts. Week 1: An
Introduction To Complexity Theory Through Its Open Questions.
|
||
| Week 1: An Introduction To Complexity Theory Through Its Open Questions.
Speakers: Steven Rudich, (Organizer), Carnegie Mellon University; Sanjeev Arora, Princeton University; Ran Raz, the Weizmann Institute of Science.
Complexity theory is a scintillating field that consistently surprises its foremost experts. There has been great success in exhibiting essential similarities between seemingly different problems. On the other hand, we have made limited progress in proving inherent differences between (seemingly different) problems. The open questions of this form are the essential mysteries of Complexity Theory. Here are some examples of the ones we will be discussing in the first week:
Week 2: Computational and proof complexity lower bounds. Speakers: Paul Beame (Organizer), University Of Washington; Michael Ben-Or, Hebrew University; Ran Raz, the Weizmann Institute of Science. The fundamental conjectures of complexity theory primarily concern the differences (as opposed to the similarities) between the complexity of various classes of computational problems. In order to prove a difference in complexity between two problems, at the very least one must demonstrate that one of the problems is hard to solve. Therefore, a significant task in complexity theory is to prove lower bounds on the complexity of specific computational problems. The three courses in week 2 examine different aspects of this research and several methods that have been successfully applied to derive lower bounds in computational and proof complexity.
Suppose that two people want to compute a function of two variables and each knows the value of only one input. How many bits of information do they need to communicate with each other in order compute this function? From the study of this simple kind of problem one can obtain interesting insights into the power of different modes of computation. Furthermore, by studying the complexity of this communication one can obtain specific consequences for the complexity of circuits needed to solve natural combinatorial problems. This course will cover both the essentials of communication complexity and its connections to other aspects of computational complexity.
This course examines two parallel threads in research on complexity lower bounds. On the face of it, these threads do not have a lot in common. Circuits not only underlie conventional digital computers but they also provide excellent models in their own right for the theoretical study of computational complexity. Proofs themselves, on the other hand, appear to be very far from computational objects. However, as will be discussed in Week 1, the size of proofs is fundamentally connected with major open problems in computational complexity. This course will discuss both proof and circuit complexity and will concentrate on the convergence of techniques for analyzing them. These results also have implications for the design of methods for automated theorem-proving.
When we think of computers, we typically think of them as operating on individual bits of their data. What happens if their inputs are elements of some algebraic structure such as a ring or field and we require that the operations that their algorithms perform are those, such as field or ring operations, that are natural within such an algebraic structure? This course will develop this line of questioning and show how one can apply ideas from areas such as algebraic geometry to understand the complexity of problems using such 'structured' modes of computing. |
Week 3: Randomness and Computation. Oded Goldreich (Organizer), the Weizmann Institute of Science; Madhu Sudan, Massachusetts Institute of Technology; Luca Trevisan, Columbia University; Salil Vadhan, Massachusetts Institute of Technology. The interplay between randomness and computation is a fascinating phenomenon. The two courses in week three focus on two aspects of this phenomenon: first, several notions of probabilistic proof systems, and second, a complexity theoretic approach to randomness.
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. These proof systems share a common (untraditional) feature -- they carry a probability of error; yet, this probability is explicitly bounded and can be reduced by successive application of the proof system. The gain in allowing this untraditional relaxation is substantial, as demonstrated by three well known results regarding interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs: In each of these cases, allowing a bounded probability of error makes the system much more powerful and useful than the traditional (errorless) counterparts. Focusing on the three types of proof systems mentioned above, we shall survey the basic definitions and results regarding probabilistic proofs. Our exposition will stress both the similarities and differences between the various types of probabilistic proofs.
A fresh perspective on the question of randomness has been taken in the theory of computing: It has been postulated that a distribution is pseudorandom if it cannot be distinguished from the uniform distribution by any efficient procedure. This paradigm, originally associating efficient procedures with polynomial-time algorithms, has been applied also with respect to a variety of limited classes of such distinguishing procedures. Starting with the general paradigm, we shall survey the archetypical case of pseudorandom generators (withstanding any polynomial-time distinguisher), as well as the derandomization of complexity classes such as BPP, some special-purpose generators, and related constructs. Return to PCMI Summer Session 2000
This page is archival material of the |
|
