What is the course all about?
A (slightly advanced) course in Computational Complexity Theory.Computational Complexity Theory is the study of efficient computation and its fundamental limitations. The theory helps us to state questions about resource bounded computation in a precise way and provide qualified and quantified answers to them. To state some examples, how much resources (say time or space etc) is required to solve concrete computational problems? Does the use of randomness or parallelism make computations significantly faster? Why are we interested in height of pessimism: that is saying "we cannot solve this problem in this much time !!". How can hard problems be used in a helpful way?
In addition, it turns out that the hardest thing to prove about the
models
is that they cannot solve a given problem within particular resource
constraints. Such ``lower bounds'' are currently known only when the
model is very specialized or the constraints are very severe. The quest
for such lower bounds and also matching upper bounds have led to
discovery of exciting new connections to other areas of computer science
and mathematics. Inherent limitations of the currently known techniques
is also explored on the research frontier of complexity theory.
Can I credit this course?
The pre-requisites for the course include Automata theory
(regular languages, TMs, enumeration, undecidability), basic
algorithmics (order notation, asymptotics, basic graph algorithms),
discrete mathematics (counting, graph theory, basic linear algebra).
Formally, this course is an elective offered for the M.Tech/MS/PhD course at IIT Madras. So students who are enrolled to these programs can definitely credit it. Undergrad students (B.Tech & Dual Degree) students can also opt for crediting the course after getting COT (consent of teacher) form signed.
For students who are planning to do research in algorithms and complexity theory, this is a highly recommended course. If you can (as per rules from the admin section of IIT) I strongly recommend that you credit the course rather than "auditing", mostly because crediting will automatically improve your participation in the course.
What next, after the course?
Since we have to spend some time covering the basic complexity theory
topics, we will have to skip some exciting developments in complexity
theory in this course. Here are a few directions in which one can
explore more. Each of them are worth one course on their own. I hope to
teach these topics at some point to those who are interested.
- Space Complexity.
- PCPs and Hardness of Approximation.
- Arithmetic Circuits and Lower Bounds.
- Communication Complexity
- Pseudorandomness & Derandomization.
- Frontiers in Boolean and Arithmetic Circuit Complexity
- Algebraic Complexity Theory.
Last updated on Fri May 13 21:08:49 IST 2011