Timeline for Approximate volume computation and lattice point enumeration - hardness
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Feb 6, 2018 at 18:26 | comment | added | Noah Stephens-Davidowitz | @TMM I added a parenthetical. | |
| Feb 6, 2018 at 18:26 | history | edited | Noah Stephens-Davidowitz | CC BY-SA 3.0 |
added 30 characters in body
|
| Feb 6, 2018 at 13:45 | comment | added | TMM | @Noah So SVP is not "NP-hard" (without this caveat) as stated in your answer. | |
| Feb 6, 2018 at 4:16 | comment | added | Noah Stephens-Davidowitz | @TMM Yes. No deterministic reduction is known, and it's a major open problem. | |
| Feb 5, 2018 at 0:24 | comment | added | TMM | As far as I know, SVP is only known to be NP-hard using randomized reductions, and not via a deterministic reduction. | |
| Nov 1, 2017 at 20:54 | comment | added | Sasho Nikolov | It's immediate from the definitions. Are you aware of the connection between centrally symmetric convex bodies and norms? en.wikipedia.org/wiki/Minkowski_functional | |
| Nov 1, 2017 at 20:06 | comment | added | Turbo | @SashoNikolov is there a reference for this fact connecting svp and convex bodies? | |
| Oct 27, 2017 at 7:46 | comment | added | Sasho Nikolov | The first if is a typo. Usually SVP is defined for norms, whose unit balls are convex bodies symmetric around 0; so, yes, $K = -K$. And, indeed, the second point is the unique nonzero integer point. | |
| Oct 27, 2017 at 7:24 | comment | added | Turbo | @SashoNikolov Does $K$ have to be a convex body symmetric around $0$? So the second point is essentially the unique non-zero integer point if there are exactly two lattice points? | |
| Oct 27, 2017 at 7:16 | comment | added | Turbo | @SashoNikolov Is there a reference for the "iff" fact or could this be seen directly? Is deciding $K$-norm in $P$ or is it $NP$ complete? Also I think "if the number of lattice.... iff the ..." should be "the number of lattice.... iff the ...". correct? | |
| Oct 27, 2017 at 6:32 | comment | added | Sasho Nikolov | Of course there is a relation to SVP: if the number of lattice points in $tK$ is at least $2$ iff the shortest nonzero vector has $K$-norm at most $t$. This gives hardness for a factor 2 approximation to the number of lattice points in a symmetric convex body. | |
| Oct 27, 2017 at 5:58 | history | rollback | Turbo |
Rollback to Revision 1
|
|
| Oct 27, 2017 at 5:57 | history | edited | Turbo | CC BY-SA 3.0 |
added 1 character in body
|
| Oct 27, 2017 at 5:21 | comment | added | Turbo | this is a question about counting lattice points and has no relation to SVP. Approximating SVP tells nothing about difficulty of counting lattice points approximately. | |
| Oct 26, 2017 at 3:16 | history | answered | Noah Stephens-Davidowitz | CC BY-SA 3.0 |