5 papers
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…
Summation Formulae for Binomial Moments
Marta Na Chen, Wenchang Chu
By combining the telescoping method with an algebraic relation, four classes of binomial moments are examined. Several explicit summation formulae are established.
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…