3 papers
cs.CC2026
Nonuniform QCPH Collapse Implies QCPH Collapse
Jeremy Ahrens Huang
Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a…
cs.CC2026
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…
cs.CC2024
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…