AFLB

From ResearchWiki

(Difference between revisions)
Jump to: navigation, search
(→Recently Seen on Arxiv)
(→Spring 2011)
 
(47 intermediate revisions not shown)
Line 1: Line 1:
The Algorithms For Lunch Bunch
The Algorithms For Lunch Bunch
-
'''Mon/Thu @ 1pm (starting May 20)'''
+
'''Thu @ 11am'''
'''Venue: the graphics annex'''
'''Venue: the graphics annex'''
 +
== Spring 2011 ==
 +
=== 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.
-
=== Readings===
+
=== Jan 13 ===
-
* Lattice theory (from [http://www.amazon.com/Lattice-Theory-Colloquium-Publications-Mathematical/dp/0821810251 Birkhoff]) and its applications in complexity, clustering, social choice theory, and more.
+
Qiushi: ALENEX 11 practice talk.
-
* [http://www.math.hawaii.edu/~jb/books.html Here is an online collection] of lecture notes.
+
-
* [http://users.ece.utexas.edu/~garg/f03-lat.html Lattice theory course] with a focus on CS applications
+
-
==Schedule==
+
=== Jan 20 ===
-
{|  border="1" style="width: 100%; text-align:left" class="content"
+
Jeff will discuss a simplified proof of the epsilon-approximation theorem for range spaces of bounded VC-dimension.
-
|-
+
-
! Date || Topic || Reading
+
-
|-
+
-
| May 20 || Posets || [http://www.math.hawaii.edu/~jb/math618/os1uh.pdf Chapter 1]: nice proof of Dilworth's theorem - also look at the exercises. Useful discussion of [http://users.ece.utexas.edu/~garg/f03/lattice/Scribe02.pdf representation of posets] here.
+
-
|-
+
-
| May 24 || Lattices: definition, semilattices, complete lattices, closure systems || [http://www.math.hawaii.edu/~jb/math618/os2uh.pdf Chapter 2] (I'd like to understand the point of closure systems better)
+
-
|-
+
-
| May 27 || Distributive and modular lattices || [http://www.math.hawaii.edu/~jb/math618/os8uh.pdf Chapter 8]; [http://www.math.hawaii.edu/~jb/math618/os9uh.pdf Chapter 9]. And a [[Talk:AFLB#Basic_Lattices| 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 || [http://www.math.hawaii.edu/~jb/math618/os9uh.pdf Chapter 9]
+
-
|-
+
-
| Jun 21 || ||
+
-
|}
+
-
== Other Topics ==
+
=== Jan 27 ===
-
Potential topics: (add your name to vote (as many topics as you like))
+
Suresh will do a recap of SODA 11.
-
'''Current top choices (at least two votes)'''
+
=== Feb 3 ===
-
* (Avishek, Chris, Piyush) algorithmic game theory (from [http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf this book])
+
Jeff will talk about his recent work on merge-able summaries.
-
* (Piyush, Avishek, Jeff, Josh) [http://www.amazon.com/Concentration-Measure-Analysis-Randomized-Algorithms/dp/0521884276 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)
+
 +
=== Feb 10 ===
 +
Discuss current research problems that people in the lab are working on.
-
'''General topics'''
+
=== Feb 17 ===
-
* (Chris) quantum computing (possibly from [http://abstract.cs.washington.edu/~dabacon/index.php/User:Dabacon:Teaching these notes])
+
John: "[http://arxiv.org/abs/1101.2428 Geodesics in CAT(0) Cubical Complexes], Federico Ardila, Megan Owen, and Seth Sullivant"
-
'''Complexity Theory'''
+
=== Feb 24 ===
-
* complexity theory fundamentals (almost surely from [http://theory.stanford.edu/~trevisan/cs254-10/ Luca Trevisan's ongoing class])
+
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].
-
* (Suresh) geometric flip theory (mulmuley's work on P vs NP). I suspect we'd go with [http://ramakrishnadas.cs.uchicago.edu/gctexplicit.ps this paper] and [http://video.ias.edu/csdm/pvsnp these videos] (and the associated reading material)
+
-
* (Suresh) A complexity series: [http://rjlipton.wordpress.com/2010/05/05/unique-games-a-three-act-play/ the unique games conjecture], [http://arxiv.org/abs/quant-ph/0603161 quantum computations as shortest paths] and [http://eccc.hpi-web.de/report/2009/102/ classical and quantum lower bounds]  + [http://scienceblogs.com/pontiff/2009/07/omg_qippspace.php QIP=PSPACE])
+
-
'''Analysis Tools'''
+
=== Mar 3 ===
-
* (Suresh) [http://www.cs.cmu.edu/~odonnell/boolean-analysis/ Fourier methods for boolean function analysis],
+
Amirali will talk about the [http://eccc.hpi-web.de/report/2011/015/ hardness and non-approximability of Bregman clustering problems].
-
'''Geometry'''
+
=== Mar 10 ===
-
* [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])
+
Avishek:
-
* (Josh?) computational topology ([http://www.amazon.com/Computational-Topology-Herbert-Edelsbrunner-Harer/dp/0821849255 Edelsbrunner/Harer] WARNING: Valerio teaches this class)
+
-
'''Miscellaneous'''
+
=== Mar 17 ===
 +
Parasaran:
-
== Papers for discussion ==
+
=== Mar 31 ===
 +
Amirali:
-
=== Recently Seen on Arxiv ===
+
=== Apr 7 ===
-
* [http://arxiv.org/abs/1002.2259 Constructive Algorithms for Discrepancy Minimization]. Nikhil Bansal.
+
John:
-
* [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
+
 +
=== Apr 14 ===
 +
Parasaran: SDM 11 practice talk.
-
* http://eccc.hpi-web.de/report/2010/072
+
=== Apr 21 ===
-
* [http://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/07_03_FP_0104.pdf On the Role of Distances in Defining Voting Rules]
+
Amirali:
-
=== STOC 2010 ===
+
=== Apr 28 ===
-
Add papers here that you found interesting (and link to full version if available)
+
Avishek:
-
* Efficiently Learning Mixtures of Two Gaussians. Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)
+
== Papers for discussion ==
-
* [http://arxiv.org/abs/0903.0034 Measuring Independence of Datasets]. Vladimir Braverman and Rafail Ostrovsky (UCLA)
+
-
* [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 ===
+
-
* [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

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

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.

Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/AFLB"
Personal tools