The Berkeley algorithms reading group, Summer 2002

Time: Thursdays?
Place: 606 Soda? There are usually one or more papers that you should at least look over before coming, so that we can have a more effective discussion.

Past semesters' reading group topics: Fall 2001

To subscribe or unsubscribe, click here.

Date Speaker Topic & paper reference

June 20 James Lee It is well-known that the property of excluding a fixed subgraph has a tester whose query complexity depends only on $\epsilon$ and not on the size of the graph. This follows from the regularity lemma, but the dependence on $\epsilon$ is enormous (a tower of towers in $1/\epsilon$). In last year's FOCS, Alon presented a lower-bound for non-bipartite graphs of the form $(c/\epsilon)^{c \log (c/\epsilon)}$ where c depends on the particular subgraph. Closing this gap, even for odd-length cycles, seems like a very interesting problem. In particular, there is some relation to the density of subsets of {1, 2, ..., n} which exclude an arithmetic progression of a certain length.
I will introduce the setting and the problem, show Alon's result, talk about the regularity lemma and the upper bound it gives, and perhaps talk about the impossibility of using the full power of the regularity lemma to get a significant improvement (there are some tower-type lower bounds due to Gowers, 1997).
Here is Alon's paper.

July 18 Chris Harrelson Some results and open problems for the metric labeling problem. Papers: Kleinberg and Tardos and Chekuri, Khanna, Naor, and Zosin

July 15 Robert Krauthgamer I will describe Conjecture 4.9 from "Algorithmic mechanism design" by Ronen and Nisan (available from Amir Ronen's homepage http://robotics.stanford.edu/~amirr) and will review some of their results (namely, those in Section 4).

August 1 Eran Halperin I'll talk about combinatorial problems arising from haplotype reconstruction (for those who are not familiar with the terms - it's biology related...)

August 8 Ronen Gradwohl I'll talk about a max flow algorithm with nonuniform random sampling. The main paper is Karger and Levine's "Random Sampling in Residual Graphs", but Benczur and Karger's "Approximate s-t min-cuts in O(n^2) time" is also useful.

August 15 Kunal Talwar I will talk about "PRIMES is in P" tomorrow. In case you haven't heard, Manindra Agarwal et.al. recently announced the first (unconditional) deterministic polynomial time algorithm for testing primality. I'll try to give an overview of the algorithm, and hope that some people who really know number theory will be around to help.

August 22 Kris Hildrum Her research on distributed nearest neighbor algorithms in certain metrics.

August 29 Jittat Fakcharoenphol I will continue a series of discussions on algorithm for finding nearest neighbors by presenting a paper by Karger and Ruhl. This topic is closely related to what Kris presented last week, because, like Kris and Satish, they consider the problem in a growth-restricted metrics. I will talk about their search data structures, called metric skip lists, and how it performs searching tasks. If time permits (in the sense that I have enough time to talk and to prepare), I will talk about how to dynamically maintain the data structures.

September 5 Elitza Maneva

September 12 Kevin Chen

Date	Speaker	Topic & paper reference
June 20	James Lee	It is well-known that the property of excluding a fixed subgraph has a tester whose query complexity depends only on $\epsilon$ and not on the size of the graph. This follows from the regularity lemma, but the dependence on $\epsilon$ is enormous (a tower of towers in $1/\epsilon$). In last year's FOCS, Alon presented a lower-bound for non-bipartite graphs of the form $(c/\epsilon)^{c \log (c/\epsilon)}$ where c depends on the particular subgraph. Closing this gap, even for odd-length cycles, seems like a very interesting problem. In particular, there is some relation to the density of subsets of {1, 2, ..., n} which exclude an arithmetic progression of a certain length. I will introduce the setting and the problem, show Alon's result, talk about the regularity lemma and the upper bound it gives, and perhaps talk about the impossibility of using the full power of the regularity lemma to get a significant improvement (there are some tower-type lower bounds due to Gowers, 1997). Here is Alon's paper.
July 18	Chris Harrelson	Some results and open problems for the metric labeling problem. Papers: Kleinberg and Tardos and Chekuri, Khanna, Naor, and Zosin
July 15	Robert Krauthgamer	I will describe Conjecture 4.9 from "Algorithmic mechanism design" by Ronen and Nisan (available from Amir Ronen's homepage http://robotics.stanford.edu/~amirr) and will review some of their results (namely, those in Section 4).
August 1	Eran Halperin	I'll talk about combinatorial problems arising from haplotype reconstruction (for those who are not familiar with the terms - it's biology related...)
August 8	Ronen Gradwohl	I'll talk about a max flow algorithm with nonuniform random sampling. The main paper is Karger and Levine's "Random Sampling in Residual Graphs", but Benczur and Karger's "Approximate s-t min-cuts in O(n^2) time" is also useful.
August 15	Kunal Talwar	I will talk about "PRIMES is in P" tomorrow. In case you haven't heard, Manindra Agarwal et.al. recently announced the first (unconditional) deterministic polynomial time algorithm for testing primality. I'll try to give an overview of the algorithm, and hope that some people who really know number theory will be around to help.
August 22	Kris Hildrum	Her research on distributed nearest neighbor algorithms in certain metrics.
August 29	Jittat Fakcharoenphol	I will continue a series of discussions on algorithm for finding nearest neighbors by presenting a paper by Karger and Ruhl. This topic is closely related to what Kris presented last week, because, like Kris and Satish, they consider the problem in a growth-restricted metrics. I will talk about their search data structures, called metric skip lists, and how it performs searching tasks. If time permits (in the sense that I have enough time to talk and to prepare), I will talk about how to dynamically maintain the data structures.
September 5	Elitza Maneva
September 12	Kevin Chen