AFLB
From ResearchWiki
The Algorithms For Lunch Bunch
Mon/Thu @ 1pm (starting May 20)
Venue: the graphics annex
Contents |
Readings
- 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
Schedule
| Date | Topic | Reading |
|---|---|---|
| May 20 | Posets | Chapter 1: nice proof of Dilworth's theorem - also look at the exercises. Useful discussion of representation of posets here. |
| May 24 | Lattices: definition, semilattices, complete lattices, closure systems | Chapter 2 (I'd like to understand the point of closure systems better) |
| May 27 | Distributive and modular lattices | Chapter 8; Chapter 9. And a question to ponder. Try not to get too distracted by the discussion of varieties and prime ideals in Chapter 8, since for finite lattices, this is all quite unnecessary. |
| Jun 7 | Modular lattices | Chapter 9 |
| Jun 21 |
Other Topics
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)
- (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.
- (1005.4033) Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
- (1005.2724) Low Rank Matrix-Valued Chernoff Bounds and Applications. Avner Magen, Anastasios Zouzias
- (0907.1054) Learning Gaussian Mixtures with Arbitrary Separation. Mikhail Belkin, Kaushik Sinha
- (1005.1122) Estimating small frequency moments of data stream: a characteristic function approach. Sumit Ganguly, Purushottam Kar
- (1005.1120) Estimating small moments of data stream in nearly optimal space-time. Sumit Ganguly
- (1005.0982) Incidences in Three Dimensions and Distinct Distances in the Plane. György Elekes, Micha Sharir
- (1005.0921) No embedding of the automorphisms of a topological space into a compact metric space endows them with a composition that passes to the limit. Patrizio Frosini, Claudia Landi
- (1004.5049) The Burbea-Rao and Bhattacharyya centroids. Frank Nielsen, Sylvain Boltz
- (1004.4223) Settling the Polynomial Learnability of Mixtures of Gaussians. Ankur Moitra, Gregory Valiant
- (1004.3486) Convergent discrete Laplace-Beltrami operators over surfaces. Jyh-Yang Wu, Mei-Hsiu Chi, Sheng-Gwo Chen
- (1004.3018) The Convex Hull of a Variety. Kristian Ranestad, Bernd Sturmfels
- (1004.2958) On the Fermat-Weber Point of a Polygonal Chain. Bhaswar B. Bhattacharya
- (1005.2638) Hierarchical Clustering for Finding Symmetries and Other Patterns in Massive, High Dimensional Datasets. Fionn Murtagh, Pedro Contreras
- (1005.0188) Generative and Latent Mean Map Kernels. Nishant A. Mehta, Alexander G. Gray
- (1005.3292) Optimization of Surface Registrations using Beltrami Holomorphic Flow. L.M. Lui, T.W. Wong, W. Zeng, X.F. Gu, P.M. Thompson, T.F. Chan, S.T. Yau
- (1005.5462) On the clustering aspect of nonnegative matrix factorization. Andri Mirzal, Masashi Furukawa
- (1005.5513) Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform. Nir Ailon, Edo Liberty
- (1006.1288) Regression on fixed-rank positive semidefinite matrices: a Riemannian approach. Gilles Meyer, Silvere Bonnabel, Rodolphe Sepulchre
- (0807.4462) Riemannian Metric and Geometric Mean for Positive Semidefinite Matrices of Fixed Rank. Silvere Bonnabel, Rodolphe Sepulchre
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.
