mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » November 2016 » Lukas Kavouras Anonymously browsing from 54.224.214.93 at 13:50:52, 23-09-2017. login
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

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.