Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

Details Dispersion of Mass and the Complexity of Randomized Geometric Algorithms Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

2006-08-12

arxiv.org/abs/cs/0608054v2

Computer Science

Computational Complexity

Full version of L. Rademacher, S. Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. Proc. 47t

Scientific paper

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in R^n (the current best algorithm has complexity roughly n^4, conjectured to be n^3). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.

Affiliated with

Also associated with

No associations

Rating

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms 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 Dispersion of Mass and the Complexity of Randomized Geometric Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dispersion of Mass and the Complexity of Randomized Geometric Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-251753