4 papers · 1 filter
Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
Jeremy Huang, Young Kun Ko, Chunhao Wang
In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to th…
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…
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 , the goal is to pre-pro…
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 - problem) to for and fi…