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

We will concentrate less on the applications as a part of the course though, while we mention some of them.

Syllabus:

  • Basic and Extremal Combinatorics: Pigeonhole principle, Double Counting, The principle of inclusion and exclusion, Mobius inversion, generating functions. Ramsey Theory. Turan's theorem. Erdos-Stone-Simonovits theorem.
  • Algebraic Methods Group Theoretic Methods. Permutation groups, Burnside Lemma. Polyas theory. The cycle index. Polyas enumeration formula.
    Dilworth's theorem, Lattices, Mobius Inversion for Lattices. Sperner’s Theorem.
    Linear Algebraic Methods: Oddtown Problem. Points in general position. The Ray-Chaudhuri-Wilson Theorem, Helly-Type theorems for finite sets. Sensivitiy Theorem.
    Polynomial Method.
    Tensor Product Methods, Wedge product methods.
  • Analytic & Spectrial Methods Fourier analysis on the hypercube. Influence and derivatives. Total influence. Noise stability. Arrow's Theorem. Noise operator, the Kahn-Kalai-Linial Theorem and the Friedgut Theorem, The Hypercontractivity Theorem, Noise sensitivity of monotone Functions, Linear threshold functions. Majority Is Stablest. p-biased Fourier analysis, Russo-Margulis Lemma, Decision trees. Fourier analysis over other fields, Roth's Theorem. Spectral structure and learning. Constant-depth circuits.
  • 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 CS1200 (Discrete Mathematical Structures). It will also require some basics of linear algebra. Since CS students may not have a course on linear algebra as a part of the curriculum, we will be building the basics required from scratch (some of the basics might be through reading assignments).

    Evaluation:

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


    Problem Sets (40%)   Scribing (10%)   Presentation (20%)   Midsem/Endsem (takehome) Exam+Viva (30%)