CS747 - Randomized Methods in Computational Complexity (Sem II, 2014-15)

 

Instructor: Nitin Saxena

TAs: Rohit Gurjar, Shubham Sahai

Office: RM 203

Lectures: T(10:30-12), Th(12-13:30) ; CS103

Office Hours: TBA

Email: nitin [at] iitk . ac . in


COURSE DESCRIPTION

In this course we will study how randomness helps in designing algorithms and how randomness can be removed from algorithms.

We will start by formalizing computation in terms of algorithms and circuits. We will see an example of randomized algorithms, identity testing, and prove that eliminating randomness would require proving hardness results. We then prove a hardness result for the problem of parity using randomized methods. We construct certain graphs called expanders that are useful in reducing randomness in algorithms. These lead to a surprising logarithmic-space algorithm for checking connectivity in graphs.

We show that if there is hardness in nature then randomness cannot exist! This we prove by developing  pseudo-random generators and error-correcting codes. We show how to extract randomness from a weakly random source by using extractors. Finally, we show how to probabilistically check proofs (PCP) and prove the hardness of approximating some NP-hard problems.


Prerequisites: Theory of Computation, Algebra.

Text Book: Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach,  http://www.cs.princeton.edu/theory/complexity/


RECENT UPDATE


[18-Apr-15] EndSem due on 25-Apr-2015.

[25-Mar-15] Assignment 3 due on 07-Apr-2015.

[13-Feb-15] MidSem due on 22-Feb-2015.

[02-Feb-15] Assignment 2 due on 12-Feb-2015.

[12-Jan-15]
Assignment 1 due on 27-Jan-2015.

[26-Oct-14]
  Course begins on Tue, 30-Dec-14.