Duke Wiki  logo
Child pages
  • Theory Reading Group, Fall 2013

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

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.

Meeting Time and Location: Fridays 10 – 11:30 am

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 am Sungjin ImConstructive Discrepancy Minimization by walking on the edges, Shachar Lovett and Raghu Meka, FOCS 2012.http://arxiv.org/pdf/1203.5747v2.pdf
09/13/1310:00 am Janardhan Kulkarni  
09/20/1310:00 am Kamesh Munagala

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

http://theoryofcomputing.org/articles/v008a006/
09/27/1310:00 am    
10/04/1310:00 am    
10/11/1310:00 am    
10/18/1310:00 am    
10/25/1310:00 am  FOCS 2013 @ Berkeley, CA. 
11/01/1310:00 am  STOC 2014 deadline (possibly). 
11/08/1310:00 am  STOC 2014 deadline (possibly). 
11/15/1310:00 am    
11/22/13110:00 am