AFLB

From ResearchWiki

Revision as of 06:51, 24 August 2010 (view source) Schizoid (Talk | contribs) ← Older edit		Latest revision as of 03:10, 23 February 2011 (view source) Parasaran (Talk | contribs) (→Spring 2011)
(43 intermediate revisions not shown)
Line 1:		Line 1:
	The Algorithms For Lunch Bunch		The Algorithms For Lunch Bunch
-	'''Thu @ 1pm (starting Aug 26, 2010)'''	+	'''Thu @ 11am'''
	'''Venue: the graphics annex'''		'''Venue: the graphics annex'''
-	== Fall 2010 ==	+	== Spring 2011 ==
-	=== Aug 26 ===	+	=== Jan 6 ===
		+	Amirali will talk about the new [http://arxiv.org/abs/1012.1240 lower bound epsilon net results by Pach and Tardos].(Also, some previous work/background over [http://infoscience.epfl.ch/record/129411/files/rectangles081707.pdf here]. Also on the agenda is the plan for the spring algorithms seminar.
-	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.	+	=== Jan 13 ===
		+	Qiushi: ALENEX 11 practice talk.
-	== Papers for discussion ==	+	=== Jan 20 ===
		+	Jeff will discuss a simplified proof of the epsilon-approximation theorem for range spaces of bounded VC-dimension.
-	=== Recently Seen on Arxiv ===	+	=== Jan 27 ===
-	* [http://arxiv.org/abs/1002.2259 Constructive Algorithms for Discrepancy Minimization]. Nikhil Bansal.	+	Suresh will do a recap of SODA 11.
-	* [http://arxiv.org/abs/1005.4033 (1005.4033) Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity]. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak	+
-	* [http://arxiv.org/abs/1005.2724 (1005.2724) Low Rank Matrix-Valued Chernoff Bounds and Applications]. Avner Magen, Anastasios Zouzias	+
-	* [http://arxiv.org/abs/0907.1054 (0907.1054) Learning Gaussian Mixtures with Arbitrary Separation]. Mikhail Belkin, Kaushik Sinha	+
-	* [http://arxiv.org/abs/1005.1122 (1005.1122) Estimating small frequency moments of data stream: a characteristic function approach]. Sumit Ganguly, Purushottam Kar	+
-	* [http://arxiv.org/abs/1005.1120 (1005.1120) Estimating small moments of data stream in nearly optimal space-time]. Sumit Ganguly	+
-	* [http://arxiv.org/abs/1005.0982 (1005.0982) Incidences in Three Dimensions and Distinct Distances in the Plane]. György Elekes, Micha Sharir	+
-	* [http://arxiv.org/abs/1005.0921 (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	+
-	* [http://arxiv.org/abs/1004.5049 (1004.5049) The Burbea-Rao and Bhattacharyya centroids]. Frank Nielsen, Sylvain Boltz	+
-	* [http://arxiv.org/abs/1004.4223 (1004.4223) Settling the Polynomial Learnability of Mixtures of Gaussians]. Ankur Moitra, Gregory Valiant	+
-	* [http://arxiv.org/abs/1004.3486 (1004.3486) Convergent discrete Laplace-Beltrami operators over surfaces]. Jyh-Yang Wu, Mei-Hsiu Chi, Sheng-Gwo Chen	+
-	* [http://arxiv.org/abs/1004.3018 (1004.3018) The Convex Hull of a Variety]. Kristian Ranestad, Bernd Sturmfels	+
-	* [http://arxiv.org/abs/1004.2958 (1004.2958) On the Fermat-Weber Point of a Polygonal Chain]. Bhaswar B. Bhattacharya	+
-	* [http://arxiv.org/abs/1005.2638 (1005.2638) Hierarchical Clustering for Finding Symmetries and Other Patterns in Massive, High Dimensional Datasets]. Fionn Murtagh, Pedro Contreras	+
-	* [http://arxiv.org/abs/1005.0188 (1005.0188) Generative and Latent Mean Map Kernels]. Nishant A. Mehta, Alexander G. Gray	+
-	* [http://arxiv.org/abs/1005.3292 (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	+
-	* [http://arxiv.org/abs/1005.5462 (1005.5462) On the clustering aspect of nonnegative matrix factorization]. Andri Mirzal, Masashi Furukawa	+
-	* [http://arxiv.org/abs/1005.5513 (1005.5513) Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform]. Nir Ailon, Edo Liberty	+
-	* [http://arxiv.org/abs/1006.1288 (1006.1288) Regression on fixed-rank positive semidefinite matrices: a Riemannian approach]. Gilles Meyer, Silvere Bonnabel, Rodolphe Sepulchre	+
-	** [http://arxiv.org/abs/0807.4462 (0807.4462) Riemannian Metric and Geometric Mean for Positive Semidefinite Matrices of Fixed Rank]. Silvere Bonnabel, Rodolphe Sepulchre	+
		+	=== Feb 3 ===
		+	Jeff will talk about his recent work on merge-able summaries.
-	* [http://eccc.hpi-web.de/report/2010/072 Constructive Proofs of Concentration Bounds]. Russell Impagliazzo, Valentine Kabanets	+	=== Feb 10 ===
-	* [http://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/07_03_FP_0104.pdf On the Role of Distances in Defining Voting Rules]	+	Discuss current research problems that people in the lab are working on.
-	=== STOC 2010 ===	+	=== Feb 17 ===
-	Add papers here that you found interesting (and link to full version if available)	+	John: "[http://arxiv.org/abs/1101.2428 Geodesics in CAT(0) Cubical Complexes], Federico Ardila, Megan Owen, and Seth Sullivant"
-	* Efficiently Learning Mixtures of Two Gaussians. Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)	+	=== Feb 24 ===
-	* [http://arxiv.org/abs/0903.0034 Measuring Independence of Datasets]. Vladimir Braverman and Rafail Ostrovsky (UCLA)	+	Lorenzo Orecchia, UC Berkeley will talk on his recent SODA work: [http://www.eecs.berkeley.edu/~orecchia/academics/orecchiav.pdf Fast Spectral Algorithms for Graph Partitioning and Decomposition].
-	* [http://arxiv.org/abs/0907.3754 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 ===	+	=== Mar 3 ===
		+	Amirali will talk about the [http://eccc.hpi-web.de/report/2011/015/ hardness and non-approximability of Bregman clustering problems].
		+
		+	=== Mar 10 ===
		+	Avishek:
		+
		+	=== Mar 17 ===
		+	Parasaran:
		+
		+	=== Mar 31 ===
		+	Amirali:
		+
		+	=== Apr 7 ===
		+	John:
		+
		+	=== Apr 14 ===
		+	Parasaran: SDM 11 practice talk.
		+
		+	=== Apr 21 ===
		+	Amirali:
		+
		+	=== Apr 28 ===
		+	Avishek:
		+
		+	== Papers for discussion ==
-	* [http://www.siam.org/proceedings/soda/2009/SODA09_047_chazelleb.pdf Natural Algorithms] ([http://arxiv.org/abs/0905.4241 this one] might be easier to read) (Chazelle, SODA 09 Best paper)	+	* [[AFLB/papers|Papers]]
-	* [http://arxiv.org/abs/0903.0544 A constructive proof of the general Lovasz Local Lemma] (Moser, earlier version STOC 09 Best Student Paper)	+
-	* [http://portal.acm.org/citation.cfm?id=1536414.1536474 Affiliation Networks] (Lattanzi, Sivakumar, STOC 09)	+
-	* [http://arxiv.org/abs/0910.3376 Quantum Proofs for Classical Theorems] (Drucker, Wolf)	+
-	* [http://repository.upenn.edu/cis_reports/123/ Unique games survey] (Harb)	+
-	* Sorting and Selection with Imprecise Comparisons (Ajtai, Feldman, Hassidim, Nelson, ICALP 09)	+
-	* [http://compgeom.cs.uiuc.edu/~jeffe//pubs/surflow.html Homology Flows, Cohomology Cuts] (Chambers, Erickson and Nayyeri, STOC 09)	+
-	* [http://homepages.cwi.nl/~monique/files/lasserrefinal.ps 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 ==		==Previous Semesters ==
		+	* [[AFLB/F10|Fall 2010]]
	* [[AFLB/S10|Spring 2010]]		* [[AFLB/S10|Spring 2010]]
	* [[AFLB/F09|Fall 2009]]		* [[AFLB/F09|Fall 2009]]

---

Latest revision as of 03:10, 23 February 2011

The Algorithms For Lunch Bunch

Thu @ 11am

Venue: the graphics annex

Contents 1 Spring 2011 1.1 Jan 6 1.2 Jan 13 1.3 Jan 20 1.4 Jan 27 1.5 Feb 3 1.6 Feb 10 1.7 Feb 17 1.8 Feb 24 1.9 Mar 3 1.10 Mar 10 1.11 Mar 17 1.12 Mar 31 1.13 Apr 7 1.14 Apr 14 1.15 Apr 21 1.16 Apr 28 2 Papers for discussion 3 Previous Semesters 4 Contact

Spring 2011

Jan 6

Amirali will talk about the new lower bound epsilon net results by Pach and Tardos.(Also, some previous work/background over here. Also on the agenda is the plan for the spring algorithms seminar.

Jan 13

Qiushi: ALENEX 11 practice talk.

Jan 20

Jeff will discuss a simplified proof of the epsilon-approximation theorem for range spaces of bounded VC-dimension.

Jan 27

Suresh will do a recap of SODA 11.

Feb 3

Jeff will talk about his recent work on merge-able summaries.

Feb 10

Discuss current research problems that people in the lab are working on.

Feb 17

John: "Geodesics in CAT(0) Cubical Complexes, Federico Ardila, Megan Owen, and Seth Sullivant"

Feb 24

Lorenzo Orecchia, UC Berkeley will talk on his recent SODA work: Fast Spectral Algorithms for Graph Partitioning and Decomposition.

Mar 3

Amirali will talk about the hardness and non-approximability of Bregman clustering problems.

Mar 10

Avishek:

Mar 17

Parasaran:

Mar 31

Amirali:

Apr 7

John:

Apr 14

Parasaran: SDM 11 practice talk.

Apr 21

Amirali:

Apr 28

Avishek:

Papers for discussion

• Papers

Previous Semesters

• Fall 2010
• Spring 2010
• Fall 2009

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.