Basic Information
Course Objectives:
The aim is to help the students to gain the ability to use some of the modern tools and techniques used to address and analyse problems that one comes across while doing research in theoretical computer science. The techniques that we intend to touch upon can easily fill up a full course each on their own, but the main objective is to give exposure to the basic ideas involved.
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.
- Fourier Analysis of Boolean Functions : Fourier Transforms and fast fourier transforms. Computing fast fourier transforms. Applications to Integer Multiplications. Fourier analysis on the Boolean cube. Spectral concentration for special classes of Boolean Functions: DNFs, Decision Trees and constant-depth circuits. Applications to Learning. Derandomization via Fourier Concentration.
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%) + Midsem Exam (25%) + Presentation (15%) +Endsem Exam (30%)