2 papers
cs.CG2025
Algorithms for the Shortest Vector Problem in -dimensional Lattices, Revisited
Lihao Zhao, Chengliang Tian, Jingguo Bi +2
Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional lattices holds practical significance in cryptography and computational geometry. While simpler than its hi…
math.NT2012
Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields
Jingguo Bi, Qi Cheng, J. Maurice Rojas
We present a deterministic 2^O(t)q^{(t-2)(t-1)+o(1)} algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree <q, has a root in F_q. A coroll…