Abstract | ||
---|---|---|
The shortest vector problem (SVP) and the shortest independent vectors problem (SIVP) are two famous problems in lattices, which are usually used to evaluate the hardness of some computational problems related to lattices. It is well known that the search-SVP is equivalent to its optimization version. However, it seems very difficult to prove the equivalence between search-SIVP and optimization-SIVP. In this paper, we revisit the Successive Minima Problem (SMP), which is proved the equivalence relation with SIVP. Naturally we will consider its optimization version as to find all successive minima of a given lattice, and finally we will prove that it is equivalent to its search version. |
Year | Venue | Field |
---|---|---|
2017 | WISA | Discrete mathematics,Computational problem,Equivalence relation,Lattice (order),Computer science,Maxima and minima,Lattice problem,Theoretical computer science,Equivalence (measure theory) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Haoyu Li | 1 | 13 | 10.81 |
Yanbin Pan | 2 | 35 | 13.29 |