Princeton University Computer Science Department

Computer Science 598B AdTopCS: Algorithms & Complexity Moses Charikar

Spring 2010

Course Summary

Administrative Information

Lectures: Fri 1:30-4:30, Room: CS 301

Professor: Moses Charikar - 305 CS Building - 258-7477 moses@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Announcements

• Subscribe to the course mailing list here .
• We will sometimes reschedule class to Monday 3-6pm because of conflicts with intractability center meetings (typically on the first Friday of every month).

Lectures

• Lecture 1: (draft) notes (Scribe: Huy Nguyen)
  
  
• Lecture 2: (draft) notes (Scribe: Rong Ge)
  
  
• Lecture 3:
  Constructive Algorithms for Discrepancy Minimization
  
  

Presentation suggestions

• Higher eigenvalues of graphs
  
  
• Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities
  On the deletion channel with small deletion probability
  See also Michael Mitzenmacher's blog post .
  
  
• Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
  
  
• Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
  
  
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations
  
  
• Weighted Geometric Set Cover via Quasi-Uniform Sampling, Kasturi Varadarajan.
  
  
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms, Aleksander Madry.
  
  
• Bilipschitz snowflakes, metrics of negative type, and PSD flows, James Lee and Mohammad Moharrami.
  
  
• Almost Tight Bounds for Rumour Spreading with Conductance, Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi.
  
  
•