AFLB

From ResearchWiki

The Algorithms For Lunch Bunch

Thu @ Noon (starting Aug 26, 2010)

Venue: the graphics annex

Contents 1 Spring 2011 1.1 Jan 6 2 Fall 2010 2.1 Aug 26 2.2 Sep 2 2.3 Sep 9 2.4 Sep 16 2.5 Sep 23 2.6 Sep 30 2.7 Oct 7 2.8 Oct 21 3 Papers for discussion 4 Previous Semesters 5 Contact

Spring 2011

Jan 6

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 ε.

Stability of eps-Kernels

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

• Papers

Previous Semesters

• 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.