Y. Ko

collaborators

4 papers

cs.CC2026

An $I^c ◯ ((lo g n / lo g lo g n)^{2})$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures

Young Kun Ko

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $I^c ◯ ((lo g n / lo g lo g n)^{2})$ for the Multiphase Probl…

cs.CC2026

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Jeremy Ahrens Huang, Young Kun Ko, Chunhao Wang

We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the gap $Max$ - $Cut$ problem) to $I^^{3} - CVP_{p}$ for $I^^{3} = O (1)$ and…

cs.CC2025

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds

Young Kun Ko

We prove a general translation theorem for converting one-way communication lower bounds over a product distribution to dynamic cell-probe lower bounds. Specifically, we consider a…

cs.CC2025

Lower Bounds for Linear Operators

Young Kun Ko

We consider a static data structure problem of computing a linear operator under cell-probe model. Given a linear operator $M \in F_{2}^{m \times n}$ , the goal is to pre-pro…

An I^c◯((logn/loglogn)2) Cell-Probe Lower Bound for Dynamic Boolean Data Structures

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds

Lower Bounds for Linear Operators

An $I^c ◯ ((lo g n / lo g lo g n)^{2})$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures