AFLB
From ResearchWiki
(→Oct 21) |
(→Fall 2010) |
||
| Line 4: | Line 4: | ||
'''Venue: the graphics annex''' | '''Venue: the graphics annex''' | ||
| + | |||
| + | == Spring 2011 == | ||
| + | === Jan 7 === | ||
| + | Amirali will talk about the new [http://arxiv.org/abs/1012.1240 lower bound epsilon net results by Pach and Tardos]. Also on the agenda is the plan for the spring algorithms seminar. | ||
== Fall 2010 == | == Fall 2010 == | ||
Revision as of 02:18, 5 January 2011
The Algorithms For Lunch Bunch
Thu @ Noon (starting Aug 26, 2010)
Venue: the graphics annex
Contents |
Spring 2011
Jan 7
Amirali will talk about the new lower bound epsilon net results by Pach and Tardos. Also on the agenda is the plan for the spring algorithms seminar.
Fall 2010
Aug 26
Suresh will talk about the recent P vs NP kerfuffle, along with some background on the problem.
Sep 2
We have a double bill:
- Avishek will talk about adaptive methods for multi-task learning (abstract) (paper)
- Suresh will talk about information-theoretic repair for databases violating integrity constraints
Sep 9
- Rasmus will talk about JL on the sphere and the simplex
Sep 16
- Qiushi will talk about recent work on implementations of the Johnson-Lindenstrauss Transform
Sep 23
- Meta-Issues: Suresh will take questions on research, being in academia / industry, and other issues.
Sep 30
- Jeff will give a talk on the following joint work with Pankaj Agarwal and Hai Yu.
Stability or ε-Kernels.
Given a point set P of n points in R^d, an ε-kernel K ⊆ P is a coreset of P that approximates the convex hull of P. As a result, it has been found very useful in the past 10 years for many geometric approximation problems. In this talk I will discuss the stability of ε-kernels in two senses. The dynamic stability shows how to maintain the ε-kernel as points are inserted and removed from P. We show how to efficiently maintain K with a constant number of changes for each point added or removed from P. The approximation stability studies how the size of K can change as ε changes. This reveals structure about the optimal shape of K and how stabile it is in different dimension. In summary, our results show that K is stable for d=2,3, but for higher dimensions it can be quite unstable with respect to changes in ε.
Oct 7
Brainstorm: Suresh will throw out two problems that came up in recent conversations.
Oct 21
- Amirali will discuss some related problems dealing with epsilon-nets and centrality. Some of the material below, although the second and fourth one I might discuss more.
- Regression depth and center points Centerpoints and regression depth
- Small strong epsilon nets Extension of the centerpoint theorem Small weak epsilon nets
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.
