more on the zig zag product..

I did an impromptu lunch presentation with my research group on expanders to celebrate the Godel Prize, and in the process dug up some useful reading. There's nothing here that's new to folks familiar with the main results, but if you want a reading list to help with grasping the significance of the results, read on.

• Luca Trevisan's series on expanders and their relation to Cayley graphs (one, two, three, four)
• Terry Tao's summary of expanders inspired by an Avi Wigderson talk.
  
• My note from SODA 2007 on the Alon/Schwartz/Schapira improved analysis of the replacement product.
• Dieter van Melkebeek's course on expanders

There are some aspects of this story that are worth drawing out. First of all, it's actually possible (I think) to get the SL = L result without using the zig zag product directly. In fact, stray comment on a post by Lance suggests as much, and with the new analysis of the replacement product this might be even more likely.

This doesn't mean that the zig-zag product is useless of course. In fact, there's a wonderful 'return to start' story here, which I'll attempt to convey. Essentially, as Luca describes, many early expander constructions proceeded via taking some special non-Abelian group and constructing its Cayley graph, which was then shown to be an expander. The zig-zag product is described "combinatorially" as a construction that takes two graphs and makes a third out of them, and one advantage of this representation is that it gives more explicit expander constructions. But it turned out that at the core of this hides a group operator ! In a certain sense, the zig zag product of the Cayley graph of two groups is the Cayley graph of the semidirect product of the groups ! This is a result of Alon, Lubotsky and Wigderson.

Godel Prize

The ACM site isn't updated yet (here's the press release), but Michael M informs us that Vadhan, Reingold and Wigderson just won the Godel prize, most likely for their paper on the zig-zag graph product, which had a major role in and for Reingold's proof that SL = L. These were inspiration for Dinur's combinatorial PCP theorem.

Congratulations !

Joint distributions aren't that bad

I was reading Noam Nisan's exposition of correlated equilibria. It's interesting to note that finding a correlated equilibrium is easy: you have to solve a linear program in the relevant variables of the underlying distribution. This is in contrast to Nash equilibria.

What struck me is that this is a good example of where a joint distribution isn't that bad. In machine learning especially, trying to "learn" a joint distribution is hard firstly because the number of variables blows up, and because of nasty correlations that one has to account for. In fact, the area of variational methods often uses the trick of replacing a joint distribution by the "closest" product distribution, and optimizing over that instead.

Here though, the "replacing by a product distribution" takes you from a correlated equilibrium problem to a Nash equilibrium problem, and now the individual probabilities actually multiply, yielding a nonlinear problem that's PPAD-Complete.

Physicists understand the web better than us, part 28596

A new physics review site. via the baconmeister:

Physicists are drowning in a flood of research papers in their own fields and coping with an even larger deluge in other areas of physics. The Physical Review journals alone published over 18,000 papers last year. How can an active researcher stay informed about the most important developments in physics?

Physics highlights exceptional papers from the Physical Review journals. To accomplish this, Physics features expert commentaries written by active researchers who are asked to explain the results to physicists in other subfields. These commissioned articles are edited for clarity and readability across fields and are accompanied by explanatory illustrations.

Each week, editors from each of the Physical Review journals choose papers that merit this treatment, aided by referee comments and internal discussion. We select commentary authors from around the world who are known for their expertise and communication skills and we devote much effort to editing these commentaries for broad accessibility.

Physics features three kinds of articles: Viewpoints are essays of approximately 1000–1500 words that focus on a single Physical Review paper or PRL letter and put this work into broader context. Trends are concise review articles (3000–4000 words in length) that survey a particular area and look for interesting developments in that field. Synopses (200 words) are staff-written distillations of interesting and important papers each week. In addition, we intend to publish selected Letters to the Editor to allow readers a chance to comment on the commentaries and summaries.

Physics provides a much-needed guide to the best in physics, and we welcome your comments (physics@aps.org).

What an excellent idea !

Kindle DX

Much well-deserved drooling over the Kindle DX. The killer app is native PDF support: as Michael Trick pointed out, the earlier Kindles didn't do too well with math support (the native Kindle document format is not PDF). I could easily see myself using the DX at conferences, rather than lugging around my laptop, or (worse) printing out copies of papers I wanted.

The Kindle has a nice feature that you can email documents to a specific address and have them synced automatically to the device, but it comes at a price ($0.10/document). If you use a direct transfer over USB though, it's free of course.

What I don't understand is why this has taken so long to happen: it seems to me that the academic market is the killer market for the Kindle: can you imagine transferring ALL your PDF papers to the Kindle for reading ? not to mention books ?

p.s for those of you who will no doubt point out that other readers exist that can read PDF, and are puzzled by all the hype over the Kindle, I leave you to your Archos MP3 players and Opera browsers.

p.p.s I spotted my first Kindle in the wild a month ago at a conference. It was rather cute looking. the DX will be much larger of course.