Projects



Research Project Talks: Sign-up Sheet

Dates:
  • Project proposal draft due 10/06
  • Project proposal final due 10/08
  • Progress reports are due every Wednesday starting 10/14 and ending with 11/18
  • Research Project Write-up draft due 11/30
  • Research Project Write-up final due 12/06
  • Project Presentations: 12/01, 12/03, 12/08


Project Proposal (1-2 pages):
  • a tentative title
  • names of all group members
  • a clear description of the topic
  • a short list (1-2) of paper you plan to read (acting as a starting point)
  • some (possibly very vague) questions that seems to go beyond what is known in the literature
  • if appropriate, a list of further papers that are/seem related


How to find a topic:
  • Find a topic/paper/question related to class you are excited about. Some suggestions are below but feel free to suggest your own.
  • Find someone to work with together. It will be to be more productive and more fun. Suggested project group size is 2-3. This sheet might be helpful in finding like-minded collegues for a project: Topics/Groups Coordination Sheet


Some Topic Suggestions:
  1. Finding Independent Sets in Sparse Graphs:

    • A 4-page probabilistic method proof by James Shearer: On the Independence Number of Sparse Graphs (paper) and recent (albeit quite unrelated) algorithmic work on this question by Nikhil Bansal: Approximating independent sets in sparse graphs (SODA 2015 paper)

    • Guy Blelloch, Jeremy Fineman, Julian Shun; Greedy Sequential Maximal Independent Set and Matching are Parallel on Average (paper)


  2. Distributed / Parallel Algorithms for Computing Maximal Independent Sets
    • Mohsen Ghaffari: An Improved Distributed Algorithm for Maximal Independent Set (SODA 2016 paper)

  3. Lovasz Local Lemma:

    • Dimitris Achlioptas, Fotis Iliopoulos: The Lovasz Local Lemma as a Random Walk (paper) AND by the same authors: Focused Stochastic Local Search and the Lovasz Local Lemma (SODA 2016)

    • Haeupler, Saha, Srinivasan: New Constructive Aspects of the Lovász Local Lemma (paper) and David Harris and Aravind Srinivasan: Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution (SODA 2016)

    • Both topics are highly related to: Robin Moser and Gabor Tardos; A constructive proof of the general Lovasz Local Lemma (paper)


  4. Matrix Chernoff Bounds and Applications:

    • Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford; Uniform Sampling for Matrix Approximation; (paper)


  5. Gossip

    • Kempe, Kleinberg, Tardos show that many gossip models are submodular in who is reached based on where rumors start and that optimization techniques for submodular functions can be used to optimize objectives of gossip games: Maximizing the Spread of Influence through a Social Network (paper)


  6. Discrepancy Minimization

    • Shachar Lovett, Raghu Meka; Constructive Discrepancy Minimization by Walking on The Edges; (paper)


  7. Hypergraph and Vertex Connectivity and Sampling

    • Dmitry Kogan, Robert Krauthgamer; Sketching Cuts in Graphs and Hypergraphs; (paper)

    • Keren Censor Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, and Fabian Kuhn; Tight Bounds on Vertex Connectivity under Vertex Sampling (paper)

      Keren Censor Hillel, Mohsen Ghaffari, and Fabian Kuhn; A New Perspective on Vertex Connectivity (paper)


  8. Coding for Interactive Communication:

    • Bernhard Haeupler; Interactive Channel Capacity Revisited (paper)

    • Sridhar Rajagopalan, Leonard Schulman; A coding theorem for distributed computation (paper)


  9. (Matroid) Secretary Problem:

    • Michael Dinitz; Recent Advances on the Matroid Secretary Problem (paper)


  10. Online Matching: