AFLB

From ResearchWiki

Revision as of 14:12, 20 May 2010 (view source) Piyush (Talk | contribs) m (→Summer 2010) ← Older edit		Latest revision as of 03:10, 23 February 2011 (view source) Parasaran (Talk | contribs) (→Spring 2011)
(75 intermediate revisions not shown)
Line 1:		Line 1:
	The Algorithms For Lunch Bunch		The Algorithms For Lunch Bunch
-	Thursdays at 12:30 (during the semester)	+	'''Thu @ 11am'''
-	== Summer 2010 ==	+
-	Tentative time: Tue/Thu @ 1pm (starting May 20)	+	'''Venue: the graphics annex'''
-	Venue: TBA (probably the graphics annex)	+
-	Potential topics: (add your name to vote (as many topics as you like))	+	== 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.
-	'''Current top choices (at least two votes)'''	+	=== Jan 13 ===
-	* (Avishek, Chris, Piyush) algorithmic game theory (from [http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf this book])	+	Qiushi: ALENEX 11 practice talk.
-	* (Suresh, Jeff, Chris, Parasaran, Josh) 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.	+
-	** [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	+
-	* (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)	+
		+	=== Jan 20 ===
		+	Jeff will discuss a simplified proof of the epsilon-approximation theorem for range spaces of bounded VC-dimension.
-	'''General topics'''	+	=== Jan 27 ===
-	* (Chris) quantum computing (possibly from [http://abstract.cs.washington.edu/~dabacon/index.php/User:Dabacon:Teaching these notes])	+	Suresh will do a recap of SODA 11.
-	'''Complexity Theory'''	+	=== Feb 3 ===
-	* complexity theory fundamentals (almost surely from [http://theory.stanford.edu/~trevisan/cs254-10/ Luca Trevisan's ongoing class])	+	Jeff will talk about his recent work on merge-able summaries.
-	* (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'''	+	=== Feb 10 ===
-	* (Suresh) [http://www.cs.cmu.edu/~odonnell/boolean-analysis/ Fourier methods for boolean function analysis],	+	Discuss current research problems that people in the lab are working on.
-	'''Geometry'''	+	=== Feb 17 ===
-	* [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])	+	John: "[http://arxiv.org/abs/1101.2428 Geodesics in CAT(0) Cubical Complexes], Federico Ardila, Megan Owen, and Seth Sullivant"
-	* (Josh?) computational topology ([http://www.amazon.com/Computational-Topology-Herbert-Edelsbrunner-Harer/dp/0821849255 Edelsbrunner/Harer] WARNING: Valerio teaches this class)	+
-	'''Miscellaneous'''	+	=== Feb 24 ===
		+	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].
-	== Papers for discussion ==	+	=== Mar 3 ===
		+	Amirali will talk about the [http://eccc.hpi-web.de/report/2011/015/ hardness and non-approximability of Bregman clustering problems].
-	=== Recently Seen on Arxiv ===	+	=== Mar 10 ===
-	* [http://arxiv.org/abs/1002.2259 Constructive Algorithms for Discrepancy Minimization]. Nikhil Bansal.	+	Avishek:
-	=== STOC 2010 ===	+	=== Mar 17 ===
-	Add papers here that you found interesting (and link to full version if available)	+	Parasaran:
-	* Efficiently Learning Mixtures of Two Gaussians. Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)	+	=== Mar 31 ===
-	* [http://arxiv.org/abs/0903.0034 Measuring Independence of Datasets]. Vladimir Braverman and Rafail Ostrovsky (UCLA)	+	Amirali:
-	* [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 ===	+	=== 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.