IARCS Electronic Notes
IARCS home > ACTIVITIES > Notes
IARCS lecture notes are available through the IARCS home page or by email to <iarcs at cmi dot ac dot in>. The notes are available in electronic form (PDF, gzipped Postscript, zipped Postscript).
At present the following three sets of notes are available. If you have some course notes which you would like to add to the series, please contact the Secretary, IARCS.
Interactive Proofs
School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai 400 005, India.Email: <jaikumar at tifr dot res dot in>
The first part of these notes contain material on standard notions in computational complexity such as {\bf P}, {\bf NP}, the polynomial time hierarchy, PSPACE etc. {\bf NP} is characterized as the class of properties that have easy to verify proofs. Randomized complexity classes are introduced and their relationship with the polynomial time hierarchy is described.
The second part of the course is devoted to results on interactive proofs. Arthur-Merlin games are studied and shown to recognize all languages in PSPACE. Two prover interactive proof systems and their relationship with the probabilistically checkable proofs (PCP) is described. The characterization of {\bf NP} in terms of PCP, as well as some of its consequences to approximation algorithms, is presented in detail.
Download: PDF, gzipped Postscript, zipped Postscript.
Computational Complexity Theory
V Vinay , scribed by P.R. Subramanya
Department of Computer Science and Automation, Indian Institute of Science, Bangalore 600 012, India.Current address:
PicoPeta Simputers Pvt Ltd, 146, 5th Cross, RMV Extn, Bangalore 560 080
Email: <vinay at picopeta dot com>
The main focus of the course is Circuit Complexity. We motivate the area through illustrative examples for the constant-depth circuit classes. Circuit implementations for the Threshold, Addition, Multiplication, Iterated Addition and Iterated Multiplication are presented with this objective in mind. A few results from Number Theory are discussed along the line.
The course then gives a bird's eye view of Computational Complexity Theory. It then winds its way through Brent's result on expression trees, Barrington's result on Bounded Width Branching Programs and Ben-Or and Cleve's result on the evaluation of expression trees using 3 registers. We then move on to Savitch's Theorem and the Immerman and Szelepscenyi result.
The course then ventures on to Haastad's Switching Lemma. We motivate and prove this beautiful result that shows PARITY is not in AC${}^0$ . In the same vein we present the Voting Polynomials of Aspens et al. Razborov's Method of Approximations with its ethereal Sunflower Lemma is reserved for the end.
Download: PDF, gzipped Postscript, zipped Postscript.
An Introduction to Logic
Chennai Mathematical Institute, 92 G.N. Chetty Road, Chennai 600 017, IndiaEmail: <madhavan at cmi dot ac dot in>
These are lecture notes for an introductory course on logic aimed at graduate students in Computer Science. The notes cover techniques and results from propositional logic, modal logic, propositional dynamic logic and first-order logic. The notes are based on a course taught to first year PhD students at Chennai Mathematical Institute, Madras, during August--December, 1997.
At the moment, these notes only cover propositional logic and modal logic. Notes on the remaining topics will be ready shortly.
Download: PDF, gzipped Postscript, zipped Postscript.
Copyright (c) IARCS 2003-2024; Last Updated: 22 Sep 2003