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.
https://files.boazbarak.org/introtcs/lnotes_book.pdf
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.
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/resource-index/
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.
https://theory.cs.princeton.edu/complexity/book.pdf
[Barak] B. Barak, Introduction to Theoretical Computer Science.
https://files.boazbarak.org/introtcs/lnotes_book.pdf
https://introtcs.org/public/index.html
O. Goldreich, Computational Complexity: A Conceptual Perspective
https://www.wisdom.weizmann.ac.il/~oded/cc-drafts.html
A. Wigderson, Mathematics and Computation.
https://www.math.ias.edu/files/Book-online-Aug0619.pdf#page=1
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)
Computational Complexity
https://www.tifr.res.in/~prahladh/teaching/2020-21/complexity/
R. O’Donnell (excellent videos)
Undergrad Complexity
https://www.youtube.com/playlist?list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2
R. WIllliams Course (slides, problems)
Automata, Computability, and Complexity Theory - Spring 2020
https://people.csail.mit.edu/rrw/6.045-2020/index.html#lectures
N.H Mustafa Course (slides are excellent on basics)
Complexity Theory
https://perso.esiee.fr/~mustafan/TechnicalWritings/Complexityslides/
M. Sipser Course
Theory of Computation
https://ocw.mit.edu/courses/mathematics/18-404j-theory-of-computation-fall-2020/index.htm
M. Sudan Graduate Course (notes, advanced course)
Complexity Theory
http://people.seas.harvard.edu/~madhusudan/courses/Spring2018/
S. Vadhan Graduate Course (notes, advanced course)
Complexity Theory
http://people.seas.harvard.edu/~salil/cs221/spring14/lectures.html