First part of the course topics are here.
Second part of the course invloving advanced topics like PSPACE, Space bounded computations, Polynomial Hierarchy, Arithmetic Circuits, Boolean Function Analysis etc will be taught by Nitin Saurabh during Oct - Nov. See https://nitinsau.github.io/CT-m21-iiith.html
Assumes basic knowledge of Discrete Maths, Linear Algebra, Probability, and Algorithms. Highly recomended to brush up these concepts. Some references are given bellow:
Chapter 1. Mathematical Background, Intro. to TCS, Boaz Barak.
We will be assuming that you have read this chapter fully and will have an assignment based on it in the first week.
Mathematics for Computer Science. MIT OCW course.
This is a good long reference. You can brush topics selectively based on need.
From 15th August - 30th September, 2021
Students are expected to spent atleast 12 hrs per week. Roughly
Your intelligence cannot be measured by just a number. It is defined by your willingness to learn, solve problems and try new things.— Prof. Feynman (@ProfFeynman) April 14, 2021
You are more than just a number. Develop your skills wherever they may lead. Share your ideas. Your skills are more valuable than your grades. 🧠
S. Arora and B. Barak (2000), Computational Complexity: A Modern Approach, Cambridge University Press.
[Barak] B. Barak, Introduction to Theoretical Computer Science.
O. Goldreich, Computational Complexity: A Conceptual Perspective
A. Wigderson, Mathematics and Computation.
C. Moore & S. Mertens (2011), The Nature of Computation, Oxford University Press.
M. Sipser (2014), Introduction to Theory of Computation, Cengange Learning.
C. Papadimitriou (1994), Computational Complexity, Addison Wesley Longman.
P. Harsha & R. Saptharishi Course (videos, notes, problems)
R. O’Donnell (excellent videos)
R. WIllliams Course (slides, problems)
Automata, Computability, and Complexity Theory - Spring 2020
N.H Mustafa Course (slides are excellent on basics)
M. Sipser Course
Theory of Computation
M. Sudan Graduate Course (notes, advanced course)
S. Vadhan Graduate Course (notes, advanced course)