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:
- Constructive Discrepancy Minimization by walking on the edges, Shachar Lovett and Raghu Meka, FOCS 2012.
- Approximating Bin Packing within O(log OPT log log OPT) bins, Thomas Rothvoss, FOCS 2013.
- A Randomized Rounding Approach to the Traveling Salesman Problem, Shayan Oveis Gharan, Amin Saberi and Mohit Singh, FOCS 2011.
- Constructive Discrepancy Minimization by walking on the edges, Shachar Lovett and Raghu Meka, FOCS 2012.
Towards Linear time Algorithms for Cuts and Flows:
- Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, Aleksander Madry, FOCS 2013.
- 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. - The weighted majority algorithm
- 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. - Compressed sensing - a short proof of the main result due to Candes.
- FFT for sparse signals
- Laplacians and Graph Partitioning - Cheeger's inequality
- Non-negative matrix factorization - Computing local and global optima.
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 |