mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » May 2017 » Evangelos Anagnostopoulos Anonymously browsing from 54.225.36.143 at 08:24:51, 18-11-2017. login
download defense details: { pdf }

MSc thesis defense presentation

Evangelos Anagnostopoulos defends his MSc thesis

Date: Monday, 29 May 2017
Time: 14:00
Location: Univeristy of Athens, Department of Informatics and Telecommunications, A56
Thesis title: Polytope Membership in High Dimension
Committee:

Thesis abstract

Polytopes in optimization and sampling problems are usually given by implicit representations through oracles. The most basic oracle is the polytope membership oracle which can identify whether a query point q lies inside P or not and is often used as the basis for more complex oracles, such as the separation oracle or the boundary oracle. In this work we aim to design, implement and analyze algorithms for approximating the membership oracle in polytopes given as the intersection of halfspaces in high dimension, by trading exactness for efficiency. Previous approaches were based on classic polytope approximation techniques which, however, have complexity that scales exponentially in the dimension and are, thus, intractable in high dimension. We establish a straightforward reduction from approximate polytope membership to approximate nearest neighbor search among points and obtain complexity bounds polynomial in the dimension, by exploiting recent progress in the complexity of nearest neighbor search. We then employ this new membership oracle to obtain a solution for the boundary oracle in high dimension. Lastly, we evaluate our algorithms experimentally and report results.

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.