2 papers
cs.CC2020
Hardness of Approximate Nearest Neighbor Search under L-infinity
Young Kun Ko, Min Jae Song
We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the norm with two simple reductions. Our first reduction shows that hardness of a spec…
cs.DS2019
An Adaptive Step Toward the Multiphase Conjecture
Young Kun Ko, Omri Weinstein
In 2010, Pǎtraşcu proposed the following three-phase dynamic problem, as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures: I: Prep…