Today : Fri, Apr 19, 2024

  • No meeting

Announcements

  • Sep 19 : Quiz 1 Evaluated sheets available.
  • Sep 17 : Problem Set 2, and Quiz 1 discussion session scheduled on Sep 18, 4:45pm.
  • Sep 13 : Problem Set 3, Deadline extended to Sep 17, 8am.
  • Older announcements.
Back to Courses

Basic Information


Course Objectives:

The course is to expose the attendee to the importance, history and progress of the study the limits of computation, its connection to various concepts that they have already seen in a basic "theory of computation" course. Then the course aims to motivate and expose to the fundamental understanding of "computation under resource constraints" - more fondly called computational complexity theory. There will be a sequel course to this, which will be titled "Advanced Complexity Theory" which takes the student through a research level exposure to deeper topics in complexity theory.

Course Syllabus

  • Computability: Review of Turing Machines, view of PDAs, 2DFAs, FAs as restricted TMs and related theorems. Tape reduction, and robustness of the model. Encoding and Enumeration of Turing Machines, Undecidability. Rice-Myhill-Shapiro theorem. Relativisation. Arithmetic and Analytic Hierarchy of languages. Proof of Godel's incompleteness theorem based on computability. Kolmogorov Complexity. Resource bounded computation. Notion of a computational resource. Blum's Speedup theorem.
  • Time Complexity: Time as a resource, Linear Speedup theorem. Crossing Sequences and their applications. Hierarchy theorems. P vs NP. Time Complexity classes and their relationships. Notion of completeness, reductions. Cook-Levin Theorem. Ladner's theorem. Relativization Barrier : Baker-Gill-Solovoy theorem.
  • Space Complexity: Space as a resource. PSPACE, L and NL. Reachability Problem, Completeness results. Savitch's theorem, Inductive Counting to show Immerman-Szelepscenyi theorem. Reachability Problems, Expander Graphs, SL=L
  • Complexity of Counting & Randomization (optional) : Counting Problems. Theory of #P-completeness. The complexity classes PP, ParityP, BPP, RP, BPP is in P/poly, Toda's theorem.

Intended Audience, Pre-requisites and Sequel Courses

This course is an ideal starting point (as electives) for students interested in theoretical aspects of computation and algorithms. The pre-requisites include the basic discrete mathematics and basic theory of computation (about regular languages, CFLs etc) courses in a typical BTech CS course. (Indeed, students without this background are also welcome to attend this course, but they are requested to meet the instructor before registering for the course).

Sequel Courses: Note that this course is a strict pre-requisite for the Advanced Complexity Theory course that will be offered in the next semester. To know more about where this fits in the stream of theory courses please see here.

Advice

From our experience with this course here are some useful tips which will help to get the maximum benefit out of the course.
  • Keep at it, Don't fall behind ! - In a conceptual and theoretical material in a course (like this), it takes time for ideas to sink in. It is extremely important to put in consistent effort throughout the semester, rather than hoping to learn everything together at the end, right before the deadlines or tests. Even though we divide the course into themes, the ideas are so inexplicably connected across themes. So, even missing a few lectures, can cause difficulty.
  • Solve the problems from the problem sets ! - The problems in the problem sets are handpicked in order to ensure that you complete the thought process started in the lectures.
    Here is a useful scheme to work on the problem sets.
    • Start Early ! : Start working on the problem sets by yourself as soon as they are available. Think through possible approaches during your spare time, say while you are waiting in line (if you do !) at Tiffanys/mess. The earlier you start the more mature the thoughts will become before the deadline. In an ideal situation, you will be able to find the solution all by yourself - this is what you should strive for.
    • I am terribly stuck - what do I do? - If you were not able to solve by about 3 days before the deadline, request for a meeting with one of your ATOC-mates who is ready to discuss and who along with you is ready to cite as a collaborator for the problems (note that this does not change the grades). Collect your thoughts (and mind-blocks) on a sheet of paper (consider this as a read only tape) - and hold a meeting with your partner for a discussion. The tape is read-only - so the conversation and the details of it will not be (and should not be) recorded. Go back to solitude, reproduce the ideas which helped you get over your mind-blocks and of course cite the source. This will naturally avoid plagiarism and you definitely will learn the solution and the reason it gets you over the mindblock.
    • At any cost, submit ! : Don't be too hard on yourself by insisting that you will submit only if you get all the solutions right. Otherwise, this may lead to accumulation of problem sets to be submitted. Make sure you submit whatever you have before the deadline even if you could not solve all the problems (even with your collaborator). There will be discussion sessions for problem sets. There are things to learn out there.