AFLB

From ResearchWiki

Revision as of 20:03, 7 May 2010

The Algorithms For Lunch Bunch

Thursdays at 12:30 (during the semester)

Summer 2010

Tentative time: Tue/Thu @ 1pm (starting May 18) Venue: TBA (probably the graphics annex)

Potential topics: (add your name to vote (as many topics as you like))

General topics

• (Avishek, Parasaran) algorithmic game theory (from this book)
• (Suresh, Jeff) Lattice theory (from Birkhoff) and its applications in complexity, clustering, social choice theory, and more...

Complexity Theory

• complexity theory fundamentals (almost surely from Luca Trevisan's ongoing class)
• (Suresh) geometric flip theory (mulmuley's work on P vs NP). I suspect we'd go with this paper and these videos (and the associated reading material)
• (Suresh) the unique games conjecture (Dick Lipton's post. The base material is in papers, in any case)

Analysis Tools

• (Piyush) concentration inequalities for random variables
• (Suresh) Fourier methods for boolean function analysis (Ryan O'Donnell's class)

Quantum Computing

• quantum computing (possibly from these notes)
• classical and quantum lower bounds (some exciting new results here and QIP=PSPACE)
• (Suresh) quantum computations as shortest paths (connections to geometry that I'm personally curious about)

Geometry

• Geometric Approximations (full book)
• uncertainty in spatial data (Jeff?: I'll add stuff soon)
• computational topology (Edelsbrunner/Harer WARNING: Valerio teaches this class)

Papers for discussion

Recently Seen on Arxiv

• Constructive Algorithms for Discrepancy Minimization. Nikhil Bansal.

STOC 2010

Add papers here that you found interesting (and link to full version if available)

• Efficiently Learning Mixtures of Two Gaussians. Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)
• Measuring Independence of Datasets. Vladimir Braverman and Rafail Ostrovsky (UCLA)
• On the Geometry of Differential Privacy. Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)
• Weighted Geometric Set Cover via Quasi-Uniform Sampling. Kasturi Varadarajan (University of Iowa)
• A Sparse Johnson-Lindenstrauss Transform. Anirban Dasgupta and Ravi Kumar and Tamas Sarlos (Yahoo! Research)

Other Papers

• Natural Algorithms (this one might be easier to read) (Chazelle, SODA 09 Best paper)
• A constructive proof of the general Lovasz Local Lemma (Moser, earlier version STOC 09 Best Student Paper)
• Affiliation Networks (Lattanzi, Sivakumar, STOC 09)
• Quantum Proofs for Classical Theorems (Drucker, Wolf)
• Unique games survey (Harb)
• Sorting and Selection with Imprecise Comparisons (Ajtai, Feldman, Hassidim, Nelson, ICALP 09)
• Homology Flows, Cohomology Cuts (Chambers, Erickson and Nayyeri, STOC 09)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Monique Laurent. Mathematics of Operations Research, Vol. 28, No. 3 (May, 2003), pp. 470-496

Previous Semesters

• Spring 2010
• Fall 2009

Contact

If you are interested in giving a talk at AFLB or have questions, please feel free to send a mail to moeller@cs.utah.edu, praman@cs.utah.edu or avishek@cs.utah.edu. If you are planning to give a talk, we would really appreciate if you have an abstract ready a week before the talk is scheduled.