*Fair and balanced coverage from Adam Klivans*

To answer one of Lance's previous
posts, the Internet is definitely
harming conferences: most everyone who stayed up until 5 AM to watch the
Red
Sox beat the Yankees in 14 innings on MLB.TV has not made it to James
Lee's talk at 8:30 AM on embeddings (in fact I think I'm the only one who
did make it here). Krauthgamer, Lee, Mendel, and Naor presented a
powerful new method for constructing embeddings of finite metric spaces
called *measured descent* which, among other things, implies optimal
volume-respecting embeddings (in the sense of Feige).

I checked the registration numbers and indeed only 172 people have officially registered for the conference—that's 100 less than the registration at STOC in Chicago.

Yesterday I mentioned the winners of the best paper award. I should also
mention the best student paper award winners: Lap Chi Lau's *An Approximate
Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem* shared the prize with
Marcin Mucha and Piotr Sankowski's *Maximum Matchings via Gaussian
Elimination*. Lau's paper gives the first constant factor approximation to
the problem of finding a large collection of edge-disjoint trees that
connect an undirected multigraph. Mucha and Sankowski give a nice method
for finding maximum matchings in general graphs in time O(n^{ω})
where ω is the matrix multiplication exponent. Lovász showed how
to test for a matching in a graph using matrix multiplication, and Mucha
and Sankowski extend this and actually recover the matching.

Valiant's talk on Holographic Algorithms was well attended: he described a
new, quantum-inspired method for constructing polynomial-time algorithms
for certain counting problems. The algorithms are classical (no quantum
required) and give the first efficient solutions for problems such as
PL-Node-Bipartition: find the cardinality of a smallest subset of
vertices V' of a max-degree 3, planar graph such that deletion of V' (and
its incident edges) causes the graph to become bipartite. At the end he
gave a simple criterion for proving P = P^{#P} via these techniques!

But how are the Waffle Houses in Rome?

ReplyDeleteA correction: There were 206 total registrants, not the 172 quoted in Adam's post

ReplyDelete