Discussion Overview
The discussion revolves around the problem of certifying the shortest vector in an n-dimensional integer lattice, exploring both the complexity of verifying such a vector in polynomial time and the implications of the length of basis vectors on algorithm efficiency.
Discussion Character
- Debate/contested
- Technical explanation
- Mathematical reasoning
Main Points Raised
- Some participants question whether it is possible to certify a shortest vector in polynomial time for an n-dimensional integer lattice, particularly when considering the complexity of the problem in non-integer lattices.
- One participant notes that the problem of finding the shortest vector in a non-integer lattice is NP-hard, suggesting that polynomial time verification may not be feasible without additional constraints.
- Another participant mentions that in 2 dimensions, Gauss' basis reduction can find the shortest vector in linear time, but expresses uncertainty about similar methods in higher dimensions.
- There is a suggestion that the algorithm's time complexity should not depend on the length of the longest basis vector, as scaling the lattice could lead to misleading results.
- One participant references an algorithm that solves the shortest lattice vector problem in 2^O(n) time, arguing that this is strictly less than O(k^n) for sufficiently large k, although they express uncertainty about the details of the proofs and algorithms involved.
- A participant points to a paper discussing the limitations of the "greedy" algorithm used by Euclid and Gauss, noting that it works effectively only up to 4 dimensions.
Areas of Agreement / Disagreement
Participants express varying opinions on the feasibility of certifying the shortest vector in polynomial time, with some arguing against the dependence on the longest basis vector, while others highlight the complexity of the problem in higher dimensions. The discussion remains unresolved with multiple competing views.
Contextual Notes
There are limitations regarding the assumptions made about the nature of the lattice (integer vs. rational) and the implications of scaling on the representation of vectors. The complexity of the algorithms discussed is also not fully quantified, leaving some aspects open to interpretation.