Skip to content

Author

Yansong Feng

5 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 Nov 2026

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduct...

Yan-Song Feng, Jia-Qi Liu, Heng-Yi Luo et al. · 0 citations
Preprint Oct 2026

A counterexample to Tokareva's conjecture on sums of two bent functions

It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ an...

Yan-Song Feng, Hao Jiang, Guan-Cheng Li et al. · 1 citation · ⚡1
Preprint Nov 2026

Finding Integer Roots of Polynomials in Nearly Optimal Time

Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up...

Yan-Song Feng, Itamar Nir · 0 citations
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, Yan-Song Feng, Yanbin Pan · 2 citations
Preprint Aug 2026

CVP Is NP-Complete for Principal Cyclotomic Ideals

The cyclic results answer Micciancio's questions of whether exact decision-CVP is-hard on cyclic lattices and on a fixed family of cyclic lattices, even when restricted to full-rank principal cyclic ideals.

Jia-Qi Liu, Yan-Song Feng, Yanbin Pan · 2 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.