CS 745: Small Space Bounded Computations

CS 745: Small Space Bounded Computations

Prerequisites

CS340, CS345

Course Contents:

In this course we shall study the computational complexity of space bounded computations. In particular, we shall focus on the various models and problems in the logarithmic space domain. We shall see how some of the complexity classes in this setting are characterized by natural computational problems and also study the known relations between these classes. We shall also lookat some of the open questions in this area and discuss potential means to tackle these problems.

Topics:

1. Studying the various models of space bounded computations.
   
2. The complexity classes that arise from these modelsand the known relations between them.
   
3. Natural computational problems that characterize these classes.
   
4. Proof techniques in this area such as the double inductive counting technique, pebbling technique, derandomization, etc.
   
5. Some classical results in this area such as Immerman-Szelepscenyi Theorem, Barrington's Theorem, circuit lower bound for parity, etc.
   
6. Recent results in this area.
   
7. Open problems and future research avenues.

Books and References:

1. Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
2. Introduction to Circuit Complexity by Heribert Vollmer.
3. Research papers and other materials that we shall refer to from time to time (I shall provide the relevant documents or pointers asto where they can be found).