AFLB
From ResearchWiki
(Difference between revisions)
m |
(→Aug 26) |
||
| Line 9: | Line 9: | ||
Suresh will talk about the recent [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper P vs NP kerfuffle], along with some background on the problem. | Suresh will talk about the recent [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper P vs NP kerfuffle], along with some background on the problem. | ||
| + | |||
| + | === Sep 2 === | ||
| + | |||
| + | Rasmus will talk about JL on the simplex. | ||
== Papers for discussion == | == Papers for discussion == | ||
Revision as of 08:32, 28 August 2010
The Algorithms For Lunch Bunch
Thu @ Noon (starting Aug 26, 2010)
Venue: the graphics annex
Contents |
Fall 2010
Aug 26
Suresh will talk about the recent P vs NP kerfuffle, along with some background on the problem.
Sep 2
Rasmus will talk about JL on the simplex.
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
- Constructive Proofs of Concentration Bounds. Russell Impagliazzo, Valentine Kabanets
- On the Role of Distances in Defining Voting Rules
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.
