## Monday, September 27, 2010

### FOCS travel awards and registration deadline: Apply SOON !

Paul Beame reminds me that the FOCS early registration deadline and hotle registration deadline are coming up soon (this Thursday). Don't forget that FOCS has three tutorials on Saturday before the conference starts, by Ketan Mulmuley, Mihai Patrascu, and Tim Roughgarden (which will be on geometric complexity theory, algorithmic game theory, and how to annoy everyone with your blog - sorry Mihai, I'm joking :))

Travel awards are also still available for the conference: Quoting Paul (emphasis mine):

There is still a bunch of NSF travel support money available for students/postdocs because we can only fund one person per US institution. All the award decisions have been made at institutions where someone applied by Sept 23rd but we are still open to new applications for travel support (not including registration) from other institutions. There is no hard deadline but people should please apply ASAP (ideally by the end of this week) because we will make final decisions on awards soon.  Follow the Travel Support link at: http://www.egr.unlv.edu/~larmore/FOCS/focs2010/
p.s cstheory Q&A has been sucking up all the time that I should have been spending blogging ... ahem.. doing research. We're at 1500+ users and counting, so come on in and join Lance's students and all the others :).

## Thursday, September 02, 2010

### Geometry @ Barriers

Bill Gasarch's summary of the Barriers II workshop omitted discussion of the geometry session, and Piotr Indyk kindly agreed to write a brief summary for your entertainment. Here it is, lightly edited and with links added. If  there are talks I'm missing links for, do let me know and I'll add them in.

The "(Geo)metric Algorithms" workshop took place on Monday, August 30, at Princeton. It was the last day of the Barriers II Workshop, dedicated to geometric and metric algorithms.

Sariel Har-Peled was the opening act. He spoke about various structures in geometry that approximate properties of large point-sets, such as epsilon-nets, epsilon-approximations and core-sets. He started by stating that finding a needle in a haystack is a problem with many solutions, e.g., one can burn it down and sift through the ashes. He did not implement any of the solutions though (and the  Princeton Fire Department was very grateful for that). He finished by asking for which problems we can (efficiently) find short certificates of near-optimality.

Alex Andoni spoke next, about high-dimensional nearest neighbors. He gave an overview of the state of the art, for Euclidean and other spaces. He asked whether we can construct a partitioning of R^t into "round" cells that supports point location in poly(t) time. Such structure could make the recent theoretically-optimal Locality-Sensitive Hashing scheme practical. He was also wondering whether we can find better embeddings of various metrics (edit distance, Earth-Mover Distance) into various simpler spaces (L1 or product spaces).

Jeff Erickson was the last one before the lunch. He spoke about computational topology, focusing mostly on algorithms for bounded genus graphs.  He covered shortest paths, maxflow and mincut, charming the audience with exquisitely drawn multi-dimensional homology diagrams, and a mesh dragon (ed: what ? no bunnies?). He presented an algorithm for max flow with running time of the form (quote) "n UglyPoly(g,log n, log C)" where g is the genus, C is the capacity bound and n is the number of points. He was wondering whether there was any way to make the bound less ugly, perhaps by making the algorithm combinatorial.

After lunch, Anupam Gupta spoke about doubling metrics and their algorithmic applications. Surprisingly many geometric algorithms can be generalized to work for arbitrary such metrics. In his talk, Anupam covered labeling schemes and optimization problems. He finished by asking whether there is a PTAS for TSP in doubling metrics, generalizing the result by Arora-Mitchell for the Euclidean spaces.

Finally, James Lee talked about the sparsest cut problem and its generalizations. Progress on this problem has often led to many fascinating developments in mathematics and TCS. The problem is closely related to embeddings of certain classes of metric spaces into L1. The main question now is to determine whether the best known approximation/distortion bounds for these problems ($\sqrt{\log n}$) are optimal.

All in all it was a fun event (although I helped organizing it, so what do I know). The videos of the talks will be available shortly.

No haystacks were harmed while filming this workshop.