Young-Kun Ko

activity

20192026

collaborators

3 papers

cs.DS2026

$Ω ((lo g n / lo g lo g n)^{2})$ Lower Bounds for Dynamic Graph Problems

Young Kun Ko

We prove an $Ω ((lo g n / lo g lo g n)^{2})$ unconditional lower bound on the maximum of the update time and the query time for Pătraşcu's multiphase problem [STOC 2010] with Disjointnes…

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 $ℓ_{\infty}$ 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…

Ω((logn/loglogn)2) Lower Bounds for Dynamic Graph Problems

Hardness of Approximate Nearest Neighbor Search under L-infinity

An Adaptive Step Toward the Multiphase Conjecture

$Ω ((lo g n / lo g lo g n)^{2})$ Lower Bounds for Dynamic Graph Problems