Class Home

E0 290: Mathematical Foundations for Modern Computing (Jan-Apr 2011)

Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560 012

Instructor: Ravi Kannan

Schedule: T,Th 14:00-15:30

Venue: CSA - 117


  • Probability
  • Linear Algebra


  • 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 CNF-SAT 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.
  • Tentative Syllabus

    High-Dimensional Data. Modeling of data in a high dimensional space. High dimensional Euclidean geometry. Random projection theorem. Random Graphs. Erdos-Renyi 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 Vapnik-Chervonenkis theorem and applications. Clustering algorithms and criteria. Provable results and algorithms for k-means 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.

    Lecture Materials

    • Chapter 2 of Hopcroft-Kannan book (High dimensional data).
    • Chapter 3 of Hopcroft-Kannan book (Random graphs).
    • A new proof of the CNF-SAT independence of clauses in the smallest clause heuristic (Chapter 3).
    • Chapter 7 of Hopcroft-Kannan book (Massive data problems).
    • Chapter 6 of Hopcroft-Kannan book (Learning and VC-dimension).
    • Chapter 8 of Hopcroft-Kannan book (Clustering).
    • 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

    Other Resources

  • 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".