
E0 290: Mathematical Foundations for Modern Computing (JanApr 2011)
Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560 012
Instructor: Ravi Kannan
Schedule: T,Th 14:0015:30
Venue: CSA  117
Prerequisite:  Probability
 Linear Algebra
Text/Reading:  John Hopcroft and Ravi Kannan. "Mathematics for Modern Computing". Forthcoming. Chapters will be made available.
 Ravi Kannan and Santosh Vempala. "Spectral Algorithms", Now Publishers, 2009.
TA: Swaprava Nath
First assignment is out (Jan 18, 2011).
First assignment deadline extended.
Discussion forum in the form of a google group has been created. Please join the group for all updated discussions on the problems. This forum is for discussing among the students and clearing doubts in the problems and points discussed in the class. While joining, please mention your name, department and department email.
New proof of independence of clauses in CNFSAT is posted in Lectures.
Second assignment is out (Feb 1, 2011).
Chapter 6 notes is posted in Lectures.
Third assignment is out (Mar 3, 2011).
Chapter 8 notes is posted in Lectures.
HighDimensional Data. Modeling of data in a high dimensional space. High dimensional Euclidean geometry. Random projection theorem. Random Graphs. ErdosRenyi model, Properties of random graphs, Giant component and threshold phenomena. Random satisfiability problems. Singular Value Decomposition and its applications. Random Walks: Connections to electrical networks, convergence using eigen values and conductance measures. Foundations of Learning Theory. The perceptron algorithm, margins and support vector machines and VapnikChervonenkis theorem and applications. Clustering algorithms and criteria. Provable results and algorithms for kmeans and other criteria. Recent work on finding local communities using random walks. Massive Data Computations including streaming algorithms. Fast approximations to matrices such as the CUR approximation. Games and Economic related models and algorithms, the notion of equilibrium, its existence and computation, markets and market equilibria.
Reading:
 Chapter 2 of HopcroftKannan book (High dimensional data).
 Chapter 3 of HopcroftKannan book (Random graphs).
 A new proof of the CNFSAT independence of clauses in the smallest clause heuristic (Chapter 3).
 Chapter 7 of HopcroftKannan book (Massive data problems).
 Chapter 6 of HopcroftKannan book (Learning and VCdimension).
 Chapter 8 of HopcroftKannan book (Clustering).
Homeworks:
 Assignment I (Problems from Chapter 2 of the above notes)
Problems: 2.3, 2.7, 2.18, 2.20, 2.32 d, 2.35, 2.36
Due: January 27, 2011 February 1, 2011
 Assignment II (Problems from Chapter 3 of the above notes)
Problems: 2.17, 2.29, 2.32, 2.33
Due: February 15, 2011
 Assignment III (Problems from Chapter 7 and 6 of the above notes)
Problems: 2.1, 2.4 from the Massive Data Chapter. Also, think about how we would deal with the case when $R^TR$ is singular in our $CUR$ approximation to a matrix.
Problems: 2.1, 2.6, 2.8, 2.14 from the Learning Chapter.
Due: March 17, 2011
Santosh Vempala. "The Random Projection Method", Dimacs Series in Discrete Math.
A very similar course by Sham Kakade at UPenn. "Multivariate Analysis, Dimensionality Reduction, and Spectral Methods".
