Exact Euclidean Shortest Vector Problem (SVP) is NP-hard under deterministic polynomial-time reductions for full-rank cyclic integer lattices.
42 Michał Karpiński and Krzysztof Piecuch
7 Pith papers cite this work, alongside 414 external citations. Polarity classification is still indexing.
7
Pith papers citing it
414
external citations · external index
citation-role summary
background 2
citation-polarity summary
years
2026 7roles
background 2representative citing papers
Given a divisor q of p-1 of intermediate size, a bounded-error quantum algorithm computes n! mod p in time O~(q^c + sqrt(p/q)), breaking the square-root barrier.
A dense, spread vector set in any fixed dimension has subset sums covering almost all lattice points of its zonotope, enabling an O~(n)-time decision algorithm.
Counting spanning quasi-trees of ribbon graphs is #P-complete already for bouquets, equivalent to evaluating the interlace polynomial at (2,1), while orientable and one-nonorientable-loop cases are determinantal.
PMMSNP problems forbidding monochromatic cliques admit a full complexity dichotomy under the Rich 2-to-1 Conjecture.
For every fixed integer p≥2, decision version of maximizing a linear function over integer points of an ℓ_p ball is NP-complete; exact algorithms and CVP connections are given for the Euclidean case.
Presents a tester for abelian group property testing in the PS-model with time Õ(√|G| + 1/ε), improving on prior linear-time testers.
citing papers explorer
-
Euclidean SVP is NP-hard for Cyclic Lattices
Exact Euclidean Shortest Vector Problem (SVP) is NP-hard under deterministic polynomial-time reductions for full-rank cyclic integer lattices.
-
Quantum Algorithms for Modular Factorials
Given a divisor q of p-1 of intermediate size, a bounded-error quantum algorithm computes n! mod p in time O~(q^c + sqrt(p/q)), breaking the square-root barrier.
-
Dense Subset Sum in Multi-Dimension
A dense, spread vector set in any fixed dimension has subset sums covering almost all lattice points of its zonotope, enabling an O~(n)-time decision algorithm.
-
Counting spanning quasi-trees of ribbon graphs: determinants and #P-completeness
Counting spanning quasi-trees of ribbon graphs is #P-complete already for bouquets, equivalent to evaluating the interlace polynomial at (2,1), while orientable and one-nonorientable-loop cases are determinantal.
-
Towards infinite PCSP: a dichotomy for monochromatic cliques
PMMSNP problems forbidding monochromatic cliques admit a full complexity dichotomy under the Rich 2-to-1 Conjecture.
-
Integer Maximization over $\ell_p$ Balls: Hardness and Exact Algorithms
For every fixed integer p≥2, decision version of maximizing a linear function over integer points of an ℓ_p ball is NP-complete; exact algorithms and CVP connections are given for the Euclidean case.
-
Sublinear Time Algorithms for Abelian Group Property Testing
Presents a tester for abelian group property testing in the PS-model with time Õ(√|G| + 1/ε), improving on prior linear-time testers.