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.
Sariel's question about short certificates was intriguing and puzzling also.
ReplyDeleteepsilon-samples, epsilon-nets, and coresets are not certificates in the usual sense. They are small subsets of the input set that are guaranteed to yield nearly tight lower bounds on some set functions. Since they are certificates for monotone functions on sets, they prove lower bounds on the true answers, but that is true of ANY (small) set. However they are not true certificates because they contain no inherent information that "proves" their near-optimality (and often that is only with high probability). Such a proof is external to the sets and it isn't necessarily small at all; indeed, it is unlikely to be so.
However, there is something interesting going on - I am just not sure that "certificate" is the right way to think about things.