Today : Sat, Apr 20, 2024

  • No meeting

Announcements

  • May 11 : Grades sent to the academic section
  • May 7 : Rescehduled Student Presentation today at 4:30pm at CS36.
  • Apr 28 : The final exam + viva. The exact schedule will be announced over email.
  • Older announcements.
Back to Courses

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:

  • Probabilistic Method:
    Linearity of Expectation Applications of Markov's Inequality, universal traversal sequences. Second moments, Derandomizng RL, Chebyshev's inequality, Chernoff Bounds and applications. Lovasz Local Lemma - applications to ramsey number lower bounds, and material from alon and spencer.
  • Explicit constructions:
    Construction of d-wise independent sample spaces, Method of conditional probabilities. Construction of extractors, even suboptimal ones, but main thing is to motivate the constructions. Expander graph construction, expanders and eigen values.
  • Markov chains and Applications:
    Steady-state probability distributions, canonical paths, conductance, coupling and mixing times, approximate counting and sampling.
  • 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 three parameters listed in activities page with the following weightage.

Problem Sets (40%)   Scribing (20%)   Presentation (20%)   Endsem Exam+Viva (20%)