Basic Information

About the course:

There are several algorithmic problems for which we know very efficient randomized algorithms (algorithms that toss pure unbiased coins during its execution and use the outcome, for its computation) but we do not know deterministic efficient algorithms. Hence it is an important task to explore methods of "derandomizing" randomized algorithms. An important abstract technique for this is what is called the "pseudorandomness", where we provide a seemingly random string when the algorithm requires to use the random bits, and the algorithm due it its efficiency constraint is unable to detect the difference between the random and pseudorandom strings provided and ends up giving the correct answer for the original problem that it was solving. This idea is developed further during the course.
It turns out this idea has more applications than what is depicted above and is related to cryptographic primitives, constructing several combinatorial objects explicitly (effectively)- hash functions, expander graphs, linear codes, extractors, dispersers, and finally what are called the pseudorandom generators, etc. ... all of which have the following common feature - if we choose a random one among the underlying objects of each type they satisfy nice properties (that we want for our application in derandomization) with high probability. However, we do not know how to deterministically efficiently construct many of them.
Naturally - it takes computational resources to "distinguish" a pseudorandom distribution from a completely uniform distribution and hence one can hope to start by constructing pseudorandom generators to "fool" resource-limited algorithms. While many interesting results are known, the direction presents a host of research opportunities. The course will present many of them in the lectures and it aims to take the student to the research frontier in these directions ensuring that students are equipped enough to take up research projects in those directions even after the course.

Course Syllabus

• Introduction, paradigms and basic tools: Randomized algorithms. Algorithmic derandomization - method of conditional probabilities. Abstract derandomization problem. Amplification of success probability. Non-uniformity. Pairwise independence and de-randomization. Linearity of Expectation. Tail Inequalities. Fourier analysis on the Boolean cube.
• Construction of Pseudo-random Objects: Pairwise independence and derandomization. Construction of k-wise independent sample spaces. Construction of expanders, extractors, dispersers, condensers, error correcting codes. Basic codes, constructions, and decoding algorithms. Limits on Performance of Codes. Algebraic (unique) decoding, Algebraic (list) decoding.
• Hardness vs Randomness: Circuit model of computation. Pseudoradom generators. Pseudo-randomness from circuit lower bounds. Connections between next-bit predictor and pseudo-random generators. Hybrid argument. Nisan-Wigderson generator.
• Derandomization of Restricted Computational Models: Pseudoranomness for parity computation, $epsilon$-biased spaces. Pseudorandomness for constant depth circuits, branching programs, half spaces. Pseudorandomness for space bounded computation.

Pre-requisite:

A standard discrete mathematics course which introduces basic proof techniques and combinatorial idea and an automata theory course which introduces the models of computation. The course will use a basic exposure to linear algebra and probability but we plan to quickly introduce them whenever required, but will not be exhaustive.

Grading :

The course grading will be done in extbf{absolute scale} rather than relative scale. The mark cut-offs for different grades of this course are 85, 75, 65, 55, 45 and 35 marks respectively for the corresponding pass grades. Grading comprises of the following components :

• Problem Sets (6x8 = 48%)
• Take-home Exams (2 x 15 = 30%)
• Course Project (22%)