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 1.2 Jan 13 1.3 Jan 20 1.4 Jan 27 1.5 Feb 3 1.6 Feb 10 1.7 Feb 17 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, 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 his recent work on mergeable summaries.

Feb 10

John:

Feb 17

Parasaran:

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.