mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » November 2016 » Lukas Kavouras
download defense details: { pdf }

MSc thesis defense presentation

Lukas Kavouras defends his MSc thesis

Date: Tuesday, 08 Nov 2016
Time: 14:00
Location: Univeristy of Athens, Department of Informatics and Telecommunications, A56
Thesis title: High dimensional approximate r-nets
Committee:

Thesis abstract

The construction of $r$-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate $r$-nets with respect to Euclidean distance. For any fixed $\epsilon>0$, the approximation factor is $1+\epsilon$ and the complexity is polynomial in the dimension and subquadratic in the number of points. The algorithm succeeds with high probability. More specifically, the best previously known LSH-based construction of Eppstein et al.\ \cite{EHS15} is improved in terms of complexity by reducing the dependence on $\epsilon$, provided that $\epsilon$ is sufficiently small. Our method does not require LSH but, instead, follows Valiant's \cite{Val15} approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which $r$-nets are computed efficiently and the error can be controlled. Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the $(1+\epsilon)$-approximate $k$th nearest neighbor distance in time subquadratic in the size of the input.

Reporter

Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.