Department of Computer Science & Engineering

Description:Many mathematical tools are used in frontier research in theoretical computer science. The objective of this course is to intensely train the student in a systematic manner in many of these techniques with the conceptual depth and mathematical rigor building on top of the mathematical training that they have received in their undergraduate studies.

CourseContent:Module 1: Basic and Extremal Combinatorics: Pigeonhole principle, the principle of inclusion and exclusion, Mobius inversion, generating functions. Ramsey Theory. Turan's theorem. Erdos-Stone-Simonovits theorem. Szemeredi regularity lemma and applications. Module 2: Algebraic Methods: Permutation groups, Burnside Lemma. Polya's theory. The cycle index. Polya's enumeration formula. Dilworth's theorem, Erdos-Ko-Rado theorem, Lattices, Mobius Inversion for Lattices. Polynomial Methods, Combinatorial nullstellensatz. Module 3: Spectral Methods: Eigenvalues and Laplacians. Isoperimetric problems. Interlacing, Regular graphs and line graphs, The homology of graphs, Spanning trees and associated structures, Expander graphs. Module 4: Analytical Methods: Fourier analysis on the hypercube and applications Influences and derivatives. Total influence. Noise stability. Arrow's Theorem. Spectral structure and learning. Applications to decision trees. Basics and applications of hypercontractivity.

TextBooks:Combinatorics: Topics, Techniques, Algorithms - Peter Cameron, Cambridge University Press, 1994 Extremal Combinatorics - Stasys Jukna, Second edition, Springer, 2011 Algebraic Graph Theory - Chris Godsil and Gordon Royle, Springer, 2001 Analysis of Boolean Functions - Ryan O'Donnell, Cambridge University Press, 2012