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. For each of the topics, the following picture (source) more-or-less explains what the course aims at:

Syllabus:

• Probability Toolkit:
  Linearity of Expectation Applications of Markov's Inequality, Stronger tail inequalities. Chebyshev's inequality, Chernoff-Hoeffding Bounds and applications. Martingales and applications. Azuma-Hoeffding inequality. Lovasz Local Lemma. Entropy Method.
• Pseudorandomness:
  Construction of d-wise independent sample spaces, Method of conditional probabilities. Construction of expanders, extractors. Unified view of Psedorandomness.
• Essential Coding Theory : Basic codes and constructions, Limits on Performance of Codes, Algebraic (unique) decoding, Algebraic (list) decoding, Applications in Algorithms, Data structures, and complexity theory.
• Fourier Transforms and Applications : Fourier Transforms and fast fourier transforms. Computing fast fourier transforms. Applications to Integer Multiplications. Fourier analysis on the Boolean cube and constant-depth circuits. Applications to Learning.
  

Course Pre-requisites:

The real pre-requisite is just mathematical maturity and an appreciation towards formal and analytical methods. This course will build on the framework provided by CS6030 (Mathematical Concepts for Computer Science), CS6014 (Advanced Theory of Computation) and CS5800 (Advanced Data Structures and Algorithms).

Evaluation:

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

• Problem Sets (40%)
• Midsem In-hall Exam (20%)
• Endsem Take-home Exam(20%)
• Course Project (20%)