|
Computer Science 597B
Topics in Algorithms
|
Fall 2013
|
Course Summary
Study of current research in algorithms, focusing on optimization problems. Topics are drawn from applications of mathematical programming techniques, advances in spectral methods, fast approximate algorithms for flows and approaches to go beyond worst case analysis. Other topics may be included depending on the interests of the participants.
Students will read and present recent research papers.
Prerequisite: A graduate course in algorithms, or
equivalent mathematical maturity. Listeners and auditors are
welcome with prior permission.
Administrative Information
Lectures: Tue-Thu 3:00-4:20 Room 302, CS
Bldg.
Instructor: Moses Charikar: 305
CS Building - 258-7477 moses [AT] cs.princeton.edu
Piazza: We will use Piazza for class discussions and announcements. Sign up here:
https://piazza.com/princeton/fall2013/cos597/home
Graduate Coordinator: Melissa Lawson -
310 CS Building - 258-5387 mml [AT] cs.princeton.edu
Schedule
(Updated as the semester progresses.)
Sept 12: Interlacing Families I
Sept 17, 19: Twice-Ramanujan Sparsifiers
I followed the presentation of the proof in Assaf Naor's survey of the result and some of its applications:
http://arxiv.org/abs/1101.4324
Sept 24: Interlacing Families I cont.
Technical details of the proof: established results on real rootedness I claimed earlier via theory of real stable polynomials. Also introduced the results in Interlacing Families II.
Sept 26: Interlacing Families II.
Technical details of the proof. The interesting new component (relative to Interlacing Families I) is the argument they use to bound the value of the largest root of the expected characteristic polynomial they obtain. I described the multivariate barrier argument they use, which is a generalization of the barrier argument in the Batson-Spielman-Srivastava work.
Readings
(tentative list, subject to change)
- Twice-Ramanujan Sparsifiers
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava
http://arxiv.org/abs/0808.0163
-
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Adam Marcus, Dan Spielman, Nikhil Srivastava
http://arxiv.org/abs/1304.4132
-
Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem
Adam Marcus, Dan Spielman, Nikhil Srivastava
http://arxiv.org/abs/1306.3969
-
Pipage Rounding, Pessimistic Estimators and Matrix Concentration
Nicholas J. A. Harvey, Neil Olver
http://arxiv.org/abs/1307.2274
-
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu
http://arxiv.org/abs/1301.6628
-
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
http://arxiv.org/abs/1010.2921
-
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Jonathan A. Kelner, Lorenzo Orecchia, Yin Tat Lee, Aaron Sidford
http://arxiv.org/abs/1304.2338
-
Nearly Maximum Flows in Nearly Linear Time
Jonah Sherman
http://arxiv.org/abs/1304.2077
-
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
Aleksander Madry
http://arxiv.org/abs/1307.2205
-
Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
http://arxiv.org/abs/1309.0563
-
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique
Raghu Meka, Avi Wigderson
http://arxiv.org/abs/1307.7615
-
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
http://arxiv.org/abs/1301.5584
-
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Sanjeev Arora, Rong Ge, Ankur Moitra
http://arxiv.org/abs/1308.6273