15-496/15-859X: Computer Science Theory for the Information Age, Spring 2012
- Instructors: Venkatesan Guruswami and Ravi Kannan
- Time: Tuesdays & Thursdays, 1:30-2:50 PM, WEH 5421. (First lecture on January 17, 2012)
- Office hours:
- Venkat: Tuesdays, 4:30-5:30pm
- Yuan: Wednesdays, 4:30-5:30pm
Course material
The course will be based on a draft of an upcoming book by John Hopcroft and Ravi Kannan. Chapters of the book will be posted here as the course proceeds.
Here is a draft of the table of contents of the book to give you an idea of the topics. There is no other required text for the course.
Problem sets
Course Description
In the first 50 odd years of its existence, computer science and the mathematical theory supporting it have flourished, enabling the widespread use of computing and algorithms today. Today, a fundamental change is taking place in computer science with the focus shifting from making computers useful and more towards applications. The reasons for this change are many, including the merging of computing and communication, the pervasiveness of data in digital form, and the emergence of social and sensor networks.
With this in mind, this course will aim to cover the mathematical
theory likely to be important for algorithmic applications in the next
few decades. One of the major changes is the switch from discrete
mathematics to an increased emphasis on probability, statistics,
linear algebra, high-dimensional geometry, etc. The course will cover
a spectrum of such topics, the following being a suggestive list of
possibilities:
- The geometry of high-dimensional space (concentration of measure, dimension reduction,...)
- Singular value decomposition
- Random graph models and threshold phenomena
- Markov chains and rapid mixing
- Algorithms for massive data problems (sampling,streaming)
- Graphical models and belief propagation
- Compressed sensing and coding
- Learning and VC-dimension
- Spectral methods and applications (eg. clustering)
Prerequisites/Intended audience
The course is cross-listed as a joint undergraduate/graduate course.
The course will be fast paced and theoretical, so mathematical maturity and comfort with material in 15-251 and basic algorithms is required.
The suggested prerequisites are 15-251 and 15-451. (In exceptional cases, if you haven't taken these courses at CMU but feel that you have the required mathematical background and would like to try this course, you may sign-up for the course after the obtaining the instructors' permission.)
Students who have taken 15-359 and enjoyed it are particularly encouraged to consider taking this course. The overlap with 15-359 will be small, so doing both courses in parallel is also encouraged.
Grading:
The grading will be based on roughly bi-weekly problem sets, attendance and class participation, and a final exam.
For the graduate version, a class project might be possible in lieu of the final (this is tentative, and details will be confirmed and made clear later on).
Maintained by Venkatesan Guruswami