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 | |
|---|---|---|---|---|---|
| Oct 27, 2017 at 6:57 | vote | accept | Turbo | ||
| Oct 27, 2017 at 6:57 | vote | accept | Turbo | ||
| Oct 27, 2017 at 6:57 | |||||
| Oct 27, 2017 at 6:57 | vote | accept | Turbo | ||
| Oct 27, 2017 at 6:57 | |||||
| Oct 27, 2017 at 6:57 | vote | accept | Turbo | ||
| Oct 27, 2017 at 6:57 | |||||
| Oct 27, 2017 at 6:57 | vote | accept | Turbo | ||
| Oct 27, 2017 at 6:57 | |||||
| Oct 27, 2017 at 6:46 | history | edited | Sasho Nikolov | CC BY-SA 3.0 |
added 1171 characters in body
|
| Oct 27, 2017 at 6:14 | comment | added | Turbo | still an algorithm cannot be ruled out on some non-trivial conditions .... correct? (such as may be promise approximation)? | |
| Oct 27, 2017 at 6:11 | comment | added | Sasho Nikolov | There is a very simple reason why an approximation algorithm in polynomial time is unlikely: such an algorithm would have to decide if a given polytope contains an integer point, which is the NP-hard ILP problem. Every approximation algorithm tells you if the number is zero. | |
| Oct 27, 2017 at 6:11 | comment | added | Turbo | ok,,,,,, if we prove constant factor approximation gives some collapse would it be interesting? | |
| Oct 27, 2017 at 6:09 | comment | added | Sasho Nikolov | My answers addresses the comment under the line: "If you know the number of lattice points approximately then we can guess volume approximately." I have asked an expert and there is no known constant factor approximation to the number of lattice points in a convex body. There are exact algorithms in fixed dimension (due to Barvinok), and also constant factor approximation is possible in singly exponential time. | |
| Oct 27, 2017 at 5:23 | comment | added | Turbo | sorry but I think this still does not clarify "Is there a randomized polytime algorithm for constant factor approximation for lattice point enumeration as well?". | |
| Oct 26, 2017 at 1:39 | history | edited | Sasho Nikolov | CC BY-SA 3.0 |
fixed a typo
|
| Oct 26, 2017 at 0:06 | comment | added | Sasho Nikolov | You could have a body $K$ of volume zero with an arbitrarily large number of lattice points: for example $K$ can live inside a lower dimensional subspace spanned by some subset of the basis vectors of $\cal L$. Both inequalities are tight for $\mathbb{Z}^n$ and an appropriate choice of $K$: e.g. take $K$ to be a tiny region around $0$ for the packing argument, and take $K = [-1+\varepsilon, 1-\varepsilon]^n$ for Minkowski's theorem. | |
| Oct 25, 2017 at 23:15 | comment | added | Turbo | So $|\mathcal L\cap K|$ refers to number of integer points in $K$. Then I have $$\frac{\mathrm{vol}(K)}{2^n\det({\cal L})}\le |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\det({\cal L})}$$ which is exponential gap in volume given number of lattice points. Does it give exponential gap in number of lattice points given volume (the $K+V$ is bothering me)? | |
| Oct 21, 2017 at 6:52 | history | edited | Sasho Nikolov | CC BY-SA 3.0 |
added 128 characters in body
|
| Oct 20, 2017 at 20:13 | history | answered | Sasho Nikolov | CC BY-SA 3.0 |