Tuesday, February 10, 2009

STOC accepted CG papers

The list of STOC 2009 accepted papers was posted on Friday. Happily, they also provided an html version with abstracts. Below are the computational geometry related papers I noticed on the list (and then happily stole from the html source).

  • Small-size ε-Nets for Axis-Parallel Rectangles and Boxes

    Boris Aronov, Esther Ezra and Micha Sharir

    We show the existence of ε-nets of size O((1/ε) log log (1/ε)) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in 3-space and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size O((1/ε) log log log (1/ε)) for the "dual" range space of "fat" regions and planar point sets. Plugging our bounds into the technique of Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding (primal or dual) range spaces.

  • Private Coresets

    Dan Feldman, Amos Fiat, Haim Kaplan and Kobbi Nissim

    We forge a link between coresets, that have found use in a vast host of geometric settings, and differentially private databases that can answer any number of queries without compromising privacy — queries of the same class well approximated by the coreset. Such queries imply efficient privacy preserving optimization algorithms for a wide range of optimization problems but are also of independent interest. We give (computationally inefficient) transformations from any coreset for queries with low generalized sensitivity to differentially private databases for the same queries. This greatly extends the work of Blum, Ligett, and Roth [BLR08], and McSherry and Talwar [MT07].

    We define the notion of private coresets, which are simultaneously both coresets and differentially private. We produce computationally efficient private coresets for k-median and k-mean in Rd, i.e., efficient differentially private databases for such queries. Private coresets also imply efficient coalition proof mechanisms and error resilient data structures.

    Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have a (small) additive error.

  • Explicit construction of a small ε-net for linear threshold functions

    Yuval Rabani and Amir Shpilka

    We give explicit constructions of ε nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments.

    As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c\sqrt{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c\sqrt{n}.

  • Every planar graph is the intersection graph of segments in the plane

    Jeremie Chalopin and Daniel Goncalves

    Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.

No comments: