AFLB
From ResearchWiki
(Difference between revisions)
(→Summer 2010) |
(→Summer 2010) |
||
| Line 20: | Line 20: | ||
'''Analysis Tools''' | '''Analysis Tools''' | ||
| - | * (Piyush, Avishek) [http://www.amazon.com/Concentration-Measure-Analysis-Randomized-Algorithms/dp/0521884276 concentration inequalities for random variables] | + | * (Piyush, Avishek, Jeff) [http://www.amazon.com/Concentration-Measure-Analysis-Randomized-Algorithms/dp/0521884276 concentration inequalities for random variables] |
* (Suresh) [http://www.cs.cmu.edu/~odonnell/boolean-analysis/ Fourier methods for boolean function analysis], | * (Suresh) [http://www.cs.cmu.edu/~odonnell/boolean-analysis/ Fourier methods for boolean function analysis], | ||
'''Geometry''' | '''Geometry''' | ||
* [http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/ Geometric Approximations] ([http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/book.pdf full book]) | * [http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/ Geometric Approximations] ([http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/book.pdf full book]) | ||
| - | * (Jeff, Chris) uncertainty in spatial data ( | + | * (Jeff, Chris) 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) |
* (Josh?) computational topology ([http://www.amazon.com/Computational-Topology-Herbert-Edelsbrunner-Harer/dp/0821849255 Edelsbrunner/Harer] WARNING: Valerio teaches this class) | * (Josh?) computational topology ([http://www.amazon.com/Computational-Topology-Herbert-Edelsbrunner-Harer/dp/0821849255 Edelsbrunner/Harer] WARNING: Valerio teaches this class) | ||
Revision as of 18:59, 10 May 2010
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, Chris) algorithmic game theory (from this book)
- (Suresh, Jeff, Chris) Lattice theory (from Birkhoff) and its applications in complexity, clustering, social choice theory, and more...
- (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
- (Piyush, Avishek, Jeff) concentration inequalities for random variables
- (Suresh) Fourier methods for boolean function analysis,
Geometry
- Geometric Approximations (full book)
- (Jeff, Chris) 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)
- (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.
