Duke Wiki logo
Algorithms Group in the Department of Computer Science
Child pages
  • Theory Reading Group, Fall 2013
Skip to end of metadata
Go to start of metadata

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

 

DateTimeLocationSpeakerPaperLink
09/06/1310:00 amLSRC D309Sungjin ImConstructive Discrepancy Minimization by walking on the edges, Lovett and Meka
http://arxiv.org/pdf/1203.5747v2.pdf
09/13/1310:00 amNorth 311Janardhan Kulkarni Approximating Bin Packing within O(log OPT log log OPT) bins, Rothvosshttp://arxiv.org/abs/1301.4010
09/20/1310:00 amNorth 311Kamesh Munagala

The weighted majority algorithm, and applications to fast, parallel algorithm design

http://theoryofcomputing.org/articles/v008a006/
09/27/1310:00 amNorth 311Debmalya 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/1310:00 amNorth 311Vahid Liaghat Eight-Fifth Approximation for TSP Paths, Sebohttp://arxiv.org/abs/1209.3523
10/11/1310: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/1310:00 amNorth 311Xiaoming (Nate) XuThe Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, Bilo, Flammini, and Moscardel 
10/25/1310:00 amNorth 311Vahid 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/1310:00 amNorth 311Sam Haney Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs, Goel, Kapralov and Khannahttp://arxiv.org/abs/0909.3346
11/08/13   STOC deadline 
11/15/1310:00 amNorth 311Abhinandan NathGraph Sparsification by Effective Resistances, Spielman and Srivastavahttp://arxiv.org/abs/0803.0929
11/22/1310:00 amNorth 311Nat KellA primal–dual randomized algorithm for weighted paging, Bansal, Buchbinder, and Naorhttp://www.win.tue.nl/~nikhil/pubs/paging-acm-final.pdf
12/02/1303:30 pmLSRC D344Eric PriceImproved Concentration Bounds for Count-Sketch (and more)http://arxiv.org/abs/1207.5200

 

 

  • No labels