Timeline for On GCD and lattice reduction
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2022 at 6:17 | comment | added | Turbo | @NoamD.Elkies I am not certain but is it possible given an oracle to compute length of shortest vector, we can compute the vector itself in P? Is there a way to see this? | |
| Oct 6, 2022 at 20:29 | comment | added | Turbo | @NoamElkies For that matter just like computing GCD is in P, is finding the length of the shortest vector in P in O(1) dimensions or may be in general dimensions (but finding the exact SV or exact basis is still hard even for O(1) dimensions just like finding Euclidean GCD is still hard for NC)? | |
| Oct 6, 2022 at 20:24 | comment | added | Turbo | @NoamD.Elkies So it seems Euclidean GCD NC reduces to feasilbility 2d ILP even if GCD is not known. Feasilibility O(1) ILP NC reduces to O(1) dimension basis reduction. The question here is if GCD is known then is Euclidean GCD in NC? The analogous question for SVP is if length of SV is known then is finding the SV (or for that matter the entire basis) in NC (or at least is a suitable approximation for SV or the basis (such as those for approximation factors coming from LLL) in NC)? | |
| Oct 6, 2022 at 18:43 | comment | added | Turbo | @NoamD.Elkies I think I am wrong. In dl.acm.org/doi/pdf/10.1145/72935.72948 it is shown Euclidean GCD is NC reducible to 2d feasibility ILP. But I do not see a feasibility program for O(1) SVP through this and I do not see how to get Euclidean GCD from just GCD. | |
| Oct 6, 2022 at 16:25 | comment | added | Turbo | @NoamD.Elkies I do not know how you can avoid using min objective in any fixed dimension and fixed constraint ilp to compute 2d svp. I think it is the objective which makes the programs sequential. Perhaps without objective these are in NC. So if GCD is in NC it follows extended GCD is also in NC if fixed dimension fixed constraints ilp without objective is in NC is a believable formulation I think. | |
| Oct 6, 2022 at 16:10 | comment | added | Turbo | @NoamD.Elkies please note that in the fixed dimension and fixed constraints ilp formulation there is no max or min. I think we have to use these in GCD formulation in 2d. In O(1) svp I think similar situation might be the case. Binary search which is what max or minimizing programs can do to optimize is also inherently sequential. | |
| Oct 6, 2022 at 15:49 | comment | added | Noam D. Elkies | If you assume integer linear programming (ILP) in fixed dimension then gcd may be a red herring: I think there's a known reduction of shortest vector in dimension O(1) to ILP in dimension O(1), and that reduction could already be in NC without doing any gcd's. | |
| Oct 6, 2022 at 14:54 | comment | added | Turbo | @NoamD.Elkies If GCD is in NC then if this problem cstheory.stackexchange.com/questions/51959/… is in NC we get $a,b$ in NC. From these can we say anything about $2$d svp and reduction of quadratic forms if GCD is in NC under reasonable assumptions? | |
| Oct 6, 2022 at 4:16 | comment | added | Noam D. Elkies | I'd expect that reduction of definite binary quadratic forms is like extended gcd, i.e. the computation not just of gcd(x,y) but of a,b such that gcd(x,y) = ax+by. It's not obvious to me how to get such a,b from the gcd in "NC". | |
| Oct 5, 2022 at 17:37 | comment | added | Turbo | @NoamD.Elkies Gauss' reduction of binary quadratic forms is same as shortest vector computation in 2D. Correct? If not at least is there a relation between the two? | |
| Oct 5, 2022 at 3:12 | comment | added | Turbo | Yes we can think of it that way.. Improve the $NC$ status of the shortest vector problem for $m=2$ and $m=O(1)$? And in general state something about shortest vector problem or approximation in general $m$ dimensions? | |
| Oct 5, 2022 at 2:44 | comment | added | Noam D. Elkies | Are questions 1 and 3 equivalent to asking whether an oracle for computing gcd(x,y) or for factoring makes this shortest-vector problem NC? | |
| Oct 5, 2022 at 1:30 | history | asked | Turbo | CC BY-SA 4.0 |