Author

Jia-Qi Liu

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

Let $q$ range over primes congruent to $3$ modulo $4$. Let $\zeta_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(\zeta_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[\zeta_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the $\ell_2$-norm is $\mathrm{NP}$-co...

Jia-Qi Liu, Yansong Feng, Yanbin Pan · 2 citations

Preprint Aug 2026

CVP Is NP-Complete for Principal Cyclotomic Ideals

We prove that exact Euclidean decision-CVP is $\mathsf{NP}$-complete on the coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings $R_d:=\mathbb{Z}[y]/(y^d+1)$. Our deterministic reduction from Exact Cover by 3-Sets (X3C) produces a target and a squared threshold $\Delta$ such that the cl...

Jia-Qi Liu, Yansong Feng, Yanbin Pan · 2 citations