Berkeley Algorithmists' Meetings

I am starting a new reading group at Berkeley. (Actually, I prefer the term "discussion group," since I was never too passionate about reading papers anyway; instead, I very much enjoy cafe-style discussion of open problems.)

For lack of a better name, this series will go by BAM (Berkeley Algorithmists' Meetings). Regarding coverage, I did not promise anything more specific than:

Since nobody can decide whether I'm doing complexity or algorithms, I will aim to keep this discussion group at the same level of ambiguity.

Presentations will transcend the boundaries of any single paper, as we will try to get a more comprehensive view of each topic, without getting bogged down in technicalities. We will talk amply about open problems.

I am hoping that all presentations will be transcribed as posts on this blog. Thus, feel free to request topics that you want to read about. You will get slightly less weight than the physical audience, but your comments will be heard.

The pilot meeting is this Tuesday, at 3:30pm. If you are in the area and would like to attend, check back tomorrow for the room details.

The topic for the first meeting is convolution and the FFT:

• how to think combinatorially about the FFT
• an Ω(nlg n) lower bound for arithmetic circuits with bounded coefficients [Morgenstern, JACM'73]
• an Ω(nlglg n) lower bound for offline range counting [Chazelle, STOC'95]
• discussion of open problems