Theory Reading Group, Fall 2013

Goal: The goal of the reading group is to study, in some detail, recent results in theoretical computer science that have had significant impact. Ideally, the papers that we discuss should be roughly at the level of best papers in major conferences in theoretical computer science so that they have broad appeal even outside the specific sub-areas of theory that they are part of.

Mailing List: For announcements about the reading group, please subscribe to the Algorithms Seminar Mailing List algsem@duke.edu. [Unsubscribe]

Meeting Time and Location: Fridays 10 – 11:30 am in LSRC D309

Suggested papers

Approximation Algorithms:

1. Constructive Discrepancy Minimization by walking on the edges, Shachar Lovett and Raghu Meka, FOCS 2012.
2. Approximating Bin Packing within O(log OPT log log OPT) bins, Thomas Rothvoss, FOCS 2013.
3. A Randomized Rounding Approach to the Traveling Salesman Problem, Shayan Oveis Gharan, Amin Saberi and Mohit Singh, FOCS 2011.

Towards Linear time Algorithms for Cuts and Flows:

1. Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, Aleksander Madry, FOCS 2013.
2. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations, Jonathan Kelner, Yin-Tat Lee, Lorenzo Orecchia, and Aaron Sidford.
  Nearly Maximum Flows in Nearly Linear Time, Jonah Sherman, FOCS 2013.
3. The weighted majority algorithm

Core Algorithmic Techniques in Data Analysis:

1. Non-negative matrix factorization - Computing local and global optima.
  A related question is what are good modeling assumptions for data? See Latent Dirichlet Allocations for an alternative approach.
2. Compressed sensing - a short proof of the main result due to Candes.
3. FFT for sparse signals
4. Laplacians and Graph Partitioning - Cheeger's inequality

Schedule

Date	Time	Location	Speaker	Paper	Link
09/06/13	10:00 am	LSRC D309	Sungjin Im	Constructive Discrepancy Minimization by walking on the edges, Lovett and Meka	http://arxiv.org/pdf/1203.5747v2.pdf
09/13/13	10:00 am	North 311	Janardhan Kulkarni	Approximating Bin Packing within O(log OPT log log OPT) bins, Rothvoss	http://arxiv.org/abs/1301.4010
09/20/13	10:00 am	North 311	Kamesh Munagala	The weighted majority algorithm, and applications to fast, parallel algorithm design	http://theoryofcomputing.org/articles/v008a006/
09/27/13	10:00 am	North 311	Debmalya Panigrahi	Electrical flows, Laplacian systems and faster approximation of maximum flow in undirected graphs, Christiano, Kelner, Madry, Spielman, and Teng	http://arxiv.org/abs/1010.2921
10/04/13	10:00 am	North 311	Vahid Liaghat	Eight-Fifth Approximation for TSP Paths, Sebo	http://arxiv.org/abs/1209.3523
10/11/13	10:00 am	North 311	Jiangwei Pan	A constructive proof of the general Lovász Local Lemma, Moser and Tardos	http://arxiv.org/abs/0903.0544
10/18/13	10:00 am	North 311	Xiaoming (Nate) Xu	The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, Bilo, Flammini, and Moscardel
10/25/13	10:00 am	North 311	Vahid Liaghat	Online Node-weighted Steiner Forest and Extensions via Disk Paintings, Hajiaghayi, Liaghat, and Panigrahi	http://www.cs.duke.edu/~debmalya/papers/focs13-steiner-forest.pdf
11/01/13	10:00 am	North 311	Sam Haney	Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs, Goel, Kapralov and Khanna	http://arxiv.org/abs/0909.3346
11/08/13				STOC deadline
11/15/13	10:00 am	North 311	Abhinandan Nath	Graph Sparsification by Effective Resistances, Spielman and Srivastava	http://arxiv.org/abs/0803.0929
11/22/13	10:00 am	North 311	Nat Kell	A primal–dual randomized algorithm for weighted paging, Bansal, Buchbinder, and Naor	http://www.win.tue.nl/~nikhil/pubs/paging-acm-final.pdf
12/02/13	03:30 pm	LSRC D344	Eric Price	Improved Concentration Bounds for Count-Sketch (and more)	http://arxiv.org/abs/1207.5200

Child pages

Theory Reading Group, Fall 2013