FOCS Begins

Weblog correspondent Janos Simon reports from Berkeley.

This is a pre-FOCS FOCS report, filling in for Lance.

FOCS 2006 is at Berkeley Marina, a lovely place on the Bay, with expensive sailboats next to the hotel gardens, against the beautiful backdrop of the San Francisco Bay, with the Berkeley hills on the other side. All of this even comes at a relatively cheap price.

Unfortunately the hills of Berkeley are not so near: downtown Berkeley is about 3 miles from the hotel, on the other side of train tracks and the interstate. This not only prevents one from easily strolling around the Berkeley campus and stopping at one of the nice coffeehouses or bookstores, but also makes getting dinner more of an adventure, involving a cab or a hotel shuttle. I am not complaining about the organizers: putting a conference together is a difficult balancing act, with too many constraints.

The conference itself should be excellent, with very strong papers, including the solution of the 2-player Nash equilibrium that won the best paper award. There will be three invited talks, all dealing in one way or other with Theory interacting with other areas of knowledge: tomorrow (Sunday) Karp will talk about "Theory of Computation as a Lens on the Sciences", Monday Terry Senjowski will teach us about Vision, and Tuesday Jon Kleinberg will discuss networks, social and technological. The biggest innovation relative to previous FOCS will be the presentation of Lady X and the Positive Eigenvalues, a rock concert. [For those with a historical bug, this is not an absolute first. Dexter Kozen, with Anna Karlin of the Severe Tire Damage rock band—the first to broadcast a rock concert on the internet—have in the past help expand our horizons in these directions, I believe at the Palo Alto conference, but I cannot offer precise pointers.]

The conference has parallel sessions (pros and cons have been previously and exhaustively discussed), so I will only be able to provide a very incomplete report of the papers presented. I should also add that I expect to miss many talks, not only due to my non-quantum nature and consequent lack of ability to be in two places at the same time, but also due to random phenomena: sleeping late, meeting friends, discussing ideas, wandering into the wrong lecture room, and forgetting about the time of talks I wanted to hear. So the papers I'll mention are not necessarily the ones I chose to listen to, just the ones I happened to not miss, and inferences about my taste or the quality of papers ignored would likely be mistaken.

Given that caveat, I can talk about two very nice results to be presented today. I heard them at Chicago before the conference.

The first is Tom Hayes' paper that gives a sufficient condition for certain important probabilistic models to converge rapidly. For definitions, technical details, etc read the paper. What I liked is that the paper is not only a significant technical improvement, but this seems to be the "correct" reason that lurked behind previous proofs, and this (I think) will be the proof we will teach.

The second is the paper by Belkin, Narayanan and Niyogi on estimating the surface area of a convex body. Both the area and the volume of high-dimensional convex bodies are very hard to approximate by the "natural" method of approximating the boundary by a simple smooth object: the number of parameters to do so grows too fast. For the volume, one can use random walks: an appropriate random walk on the space is stopped and we record whether we stopped inside or outside the object. The ratio of these events can be used to estimate the volume. Unfortunately this does not work for the surface area. The very cute idea of the Belkin et al paper is to put a heat source inside the object, and observe the amount of heat that leaks outside: this will be proportional to the area

Of course there are lots of technical difficulties, but they can be overcome. The details are not easy, but I thought the idea was new and nice.