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 20) Venue: TBA (probably the graphics annex)
Potential topics: (add your name to vote (as many topics as you like))
Current top choices (at least two votes)
- (Avishek, Chris, Piyush) algorithmic game theory (from this book)
- (Suresh, Jeff, Chris, Parasaran, Josh) Lattice theory (from Birkhoff) and its applications in complexity, clustering, social choice theory, and more.
- Here is an online collection of lecture notes.
- Lattice theory course with a focus on CS applications
- (Piyush, Avishek, Jeff, Josh) concentration inequalities for random variables
- (Jeff, Chris, Josh, Piyush) uncertainty in spatial data (We would follow a series of (mainly) recent papers spanning areas from Computational Geometry, databases, machine learning, to statistics. We would start with models and then move on to specific applications where they are used. We will encounter many interesting open questions. If I get more votes or upon request, I will sketch a paper list in more detail)
General topics
- (Chris) quantum computing (possibly from these notes)
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) A complexity series: the unique games conjecture, quantum computations as shortest paths and classical and quantum lower bounds + QIP=PSPACE)
Analysis Tools
Geometry
- Geometric Approximations (full book)
- (Josh?) computational topology (Edelsbrunner/Harer WARNING: Valerio teaches this class)
Miscellaneous
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.
