Basic Information

Basic Information

Course Objectives:

As the title of the course suggests this course is all about Pseudorandom objects. The main objective to lay foundation to the theory of pseudorandomness by introducing pseudorandom objects such as Pesudorandom Generators, Error Correcting Codes, Expander Graphs and Randomness Extractors with applications.

Syllabus

Probabilistic Method (Review): Linearity of Expectation, Markov's Inequality, Chebyshev's inequality, Chernoff Bounds. Lovasz Local Lemma - applications to ramsey number lower bounds.
Essential Coding Theory : Basic codes and constructions, Limits on Performance of Codes, Algebraic (unique) decoding, Algebraic (list) decoding, locally decodable codes and local list decodable codes. Applications in complexity theory. Explicit Constructions Construction of d-wise independent sample spaces. Expander graphs. Existence and Construction. Explicit construction of expander graphs. Applications. Randomness Extractors. Explicit Constructions of extractors.

Course Pre-requisites:

The real pre-requisite is just mathematical maturity and an appreciation towards formal and analytical methods. However, an exposure to Computability and Complexity CS6014 would help developing a better perspective for the course.

Evaluation:

Final score will depend on four parameters listed in activities page with the following weightage.

---

Problem Sets (30%) + Quizzes (20%) + Project Presentation (30%) +Endsem Exam (20%)

---