AFLB
From ResearchWiki
The Algorithms For Lunch Bunch
Thursdays at 12:30 (during the semester)
Contents |
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
- (Parasaran, Avishek) 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, Avishek) 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
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.
