Basic Information


Objective

The aim is to help the students to gain the ability to use some of the modern tools and techniques used to address and analyze problems in the broad area of theoretical computer science. Combinatorics will remain the undercurrent of the course. We will be learning about combinatorial, algebraic, analytical and spectral methods that are prevalent these days. The focus will be more on concepts with a limited view on applications.

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 (20%, 6% + 7% +7% ), Quiz 1 (20%), Quiz 2 (20%), Viva (10%), EndSem (30%)