Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation

Details Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation

2012-01-28

arxiv.org/abs/1201.5972v1

Computer Science

Computational Complexity

Scientific paper

We give a deterministic 2^{O(n)} algorithm for computing an M-ellipsoid of a
convex body, matching a known lower bound. This has several interesting
consequences including improved deterministic algorithms for volume estimation
of convex bodies and the shortest and closest lattice vector problems under
general norms.

Affiliated with

Also associated with

No associations

Rating

Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-257697