AFLB

From ResearchWiki

(Difference between revisions)
Jump to: navigation, search
(→Recently Seen on Arxiv)
Line 4: Line 4:
'''Venue: the graphics annex'''
'''Venue: the graphics annex'''
-
 
-
 
-
=== Readings===
 
-
* 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
 
-
 
-
==Schedule==
 
-
{|  border="1" style="width: 100%; text-align:left" class="content"
 
-
|-
 
-
! 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 ==
 
-
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 [http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf this book])
 
-
* (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)
 
-
 
-
 
-
'''General topics'''
 
-
* (Chris) quantum computing (possibly from [http://abstract.cs.washington.edu/~dabacon/index.php/User:Dabacon:Teaching these notes])
 
-
 
-
'''Complexity Theory'''
 
-
* complexity theory fundamentals (almost surely from [http://theory.stanford.edu/~trevisan/cs254-10/ Luca Trevisan's ongoing class])
 
-
* (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'''
 
-
* (Suresh) [http://www.cs.cmu.edu/~odonnell/boolean-analysis/ Fourier methods for boolean function analysis],
 
-
 
-
'''Geometry'''
 
-
* [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])
 
-
* (Josh?) computational topology ([http://www.amazon.com/Computational-Topology-Herbert-Edelsbrunner-Harer/dp/0821849255 Edelsbrunner/Harer] WARNING: Valerio teaches this class)
 
-
 
-
'''Miscellaneous'''
 
== Papers for discussion ==
== Papers for discussion ==

Revision as of 06:36, 11 August 2010

The Algorithms For Lunch Bunch

Mon/Thu @ 1pm (starting May 20)

Venue: the graphics annex

Contents

Papers for discussion

Recently Seen on Arxiv


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

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