Ernie's 3D Pancakes

Geometry and topology at ICS 2011

The list of accepted papers for the second iteration of the Innovations in Computer Science conference is out. Here is a list of the computational geometry and topology papers that were accepted.

• Optimal lower bounds for locality sensitive hashing (except when q is tiny)
  Ryan O'Donnell, Yi Wu, Yuan Zhou

Hmm. Considering who was on the program committee, I really expected this list to be a lot longer.

Geometry and topology at SODA 2011

Andrew McGregor posts a link to the list of accepted papers at SODA 2011. The list bizarrely only includes the contact authors for each paper, rather than the complete list of authors, perhaps because HotCRP (the submission system) did not actually ask for a complete list of authors for each submission.

Anyway, here is a non-exclusive, non-exhaustive list of computational geometry and topology papers that were accepted, with complete author lists when I could reconstruct them. Starred* authors are students (as far as I can tell).

Algorithms and Hardness for Subspace Approximation

Amit Deshpande, Kasturi Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi

An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

Nir Ailon and Edo Liberty

An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter

Shay Solomon*

Approximate Nearest Neighbor Search for Low Dimensional Queries

Sariel Har-Peled and Nirman Kumar*

Collapse

Uri Zwick and Günter Rote

Computing Replacement Paths in Surface Embedded Graphs

Jeff Erickson and Amir Nayyeri*

Computing Shortest Paths amid Pseudodisks

Danny Z. Chen and Haitao Wang

Convex hulls of hyperspheres and convex hulls of convex polytopes lying on parallel hyperplanes

Menelaos I. Karavelas, Eleni Tzanaki

Dimensionality Reduction: Beyond the Johnson-Lindenstrauss Bound

Yair Bartal, Benjamin Recht, and Leonard J. Schulman

Embedding Stacked Polytopes on a Polynomial Sized Grid

André Schulz (inter alia?)

Fast, precise and dynamic distance queries

Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty

I/O-Efficient contour queries on terrains

Pankaj K. Agarwal, Thomas Mølhave, and Bardia Sadri

Improved Bound for the Union of Fat Triangles

Esther Ezra and Micha Sharir

Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers

Jeff Erickson and Amir Nayyeri*

Mobile Geometric Graphs: Detection, Coverage and Percolation

Yuval Peres, Alistair Sinclair, Perla Sousi, and Alexandre Stauffer

New Approximation Algorithms for Minimum Enclosing Convex Shapes

Ankan Saha, S.V.N. Vishwanathan, and Xinhua Zhang

Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Low Error

T.S. Jayram and David Woodruff

Overlap properties of geometric expanders

Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and Janos Pach

Shortest Non-Crossing Walks in the Plane

Jeff Erickson and Amir Nayyeri*

Streaming k-means on Well-Clusterable Data

Adam Meyerson, Alan Roytman, Michael Shindler, and Brian Tagiku

Succinct Convex Greedy Drawing of 3-Connected Plane Graphs

Huaming Zhang and Xin He

The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus

Shayan Oveis Gharan* and Amin Saberi

Triangulating the Square: Quadtrees and Delaunay Triangulations are Equivalent

Maarten Löffler and Wolfgang Mulzer*