Dispersion of mass and the complexity of randomized geometric algorithms. (English) Zbl 1149.68079
Summary: 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 \(\mathbb 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.
MSC:
| 68W20 | Randomized algorithms |
| 68Q25 | Analysis of algorithms and problem complexity |
| 65Y20 | Complexity and performance of numerical algorithms |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
volume computation; lower bounds; randomized algorithms; variance hypothesis; dispersion of mass; determinant computationReferences:
| [1] | (Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions (1972), Dover: Dover New York) · Zbl 0543.33001 |
| [2] | D. Applegate, R. Kannan, Sampling and integration of near log-concave functions, in: Proc. 23rd Ann. ACM Symp. Theory Comput., 1991, pp. 156-163; D. Applegate, R. Kannan, Sampling and integration of near log-concave functions, in: Proc. 23rd Ann. ACM Symp. Theory Comput., 1991, pp. 156-163 |
| [3] | Ball, K., Normed spaces with a weak Gordon-Lewis property, Lecture Notes in Math., 1470, 36-47 (1991) · Zbl 0762.46004 |
| [4] | Bárány, I.; Füredi, Z., Computing the volume is difficult, Discrete Comput. Geom., 2, 314-326 (1987) · Zbl 0628.68041 |
| [5] | Björner, A.; Lovász, L.; Yao, A. C.-C., Linear decision trees: Volume estimates and topological bounds, (STOC (1992), ACM), 170-177 |
| [6] | Bobkov, S. G.; Koldobsky, A., On the central limit property of convex bodies, (Geometric Aspects of Functional Analysis. Geometric Aspects of Functional Analysis, Lecture Notes in Math., vol. 1807 (2003), Springer: Springer Berlin), 44-52 · Zbl 1039.52003 |
| [7] | Bourgain, J., On the distribution of polynomials on high-dimensional convex sets, (Geometric Aspects of Functional Analysis (1989-90). Geometric Aspects of Functional Analysis (1989-90), Lecture Notes in Math., vol. 1469 (1991), Springer: Springer Berlin), 127-137 · Zbl 0773.46013 |
| [8] | Dobkin, D.; Lipton, R. J., A lower bound of \(\frac{1}{2} n^2\) on linear search programs for the knapsack problem, J. Comput. System Sci., 16, 3, 413-417 (1978) · Zbl 0397.68045 |
| [9] | Dyer, M.; Frieze, A., Computing the volume of convex bodies: A case where randomness provably helps, (Probabilistic Combinatorics and Its Applications. Probabilistic Combinatorics and Its Applications, San Francisco, CA, 1991. Probabilistic Combinatorics and Its Applications. Probabilistic Combinatorics and Its Applications, San Francisco, CA, 1991, Proc. Sympos. Appl. Math., vol. 44 (1991), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 123-169 · Zbl 0754.68052 |
| [10] | Dyer, M.; Frieze, A.; Kannan, R., A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach., 38, 1, 1-17 (1991) · Zbl 0799.68107 |
| [11] | Edelman, A., Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9, 4, 543-560 (1988) · Zbl 0678.15019 |
| [12] | Elekes, G., A geometric inequality and the complexity of computing volume, Discrete Comput. Geom., 1, 4, 289-292 (1986) · Zbl 0611.52010 |
| [13] | Goldreich, O.; Levin, L. A., A hard-core predicate for all one-way functions, (STOC (1989), ACM), 25-32 |
| [14] | Jerrum, M. R.; Valiant, L. G.; Vazirani, V. V., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci., 43, 2-3, 169-188 (1986) · Zbl 0597.68056 |
| [15] | Kannan, R.; Lovász, L.; Simonovits, M., Random walks and an \(O^\ast(n^5)\) volume algorithm for convex bodies, Random Structures Algorithms, 11, 1, 1-50 (1997) · Zbl 0895.60075 |
| [16] | Lovász, L., How to compute the volume, Jber. d. Dt. Math.-Verein, Jubiläumstagung, 138-151 (1990) · Zbl 0756.52010 |
| [17] | Lovász, L.; Simonovits, M., The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, (31st Annual Symposium on Foundations of Computer Science, vols. I, II. 31st Annual Symposium on Foundations of Computer Science, vols. I, II, St. Louis, MO, 1990 (1990), IEEE Comput. Soc. Press: IEEE Comput. Soc. Press Los Alamitos, CA), 346-354 |
| [18] | Lovász, L.; Simonovits, M., Random walks in a convex body and an improved volume algorithm, Random Structures Algorithms, 4, 4, 359-412 (1993) · Zbl 0788.60087 |
| [19] | Lovász, L.; Vempala, S., Simulated annealing in convex bodies and an \(O^\ast(n^4)\) volume algorithm, J. Comput. System Sci., 72, 2, 392-417 (2006) · Zbl 1090.68112 |
| [20] | Lovász, L.; Vempala, S., The geometry of logconcave functions and sampling algorithms, Random Structures Algorithms, 30, 3, 307-358 (2007) · Zbl 1122.65012 |
| [21] | Milman, V.; Pajor, A., Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed \(n\)-dimensional space, Lecture Notes in Math., 1376, 64-104 (1989) · Zbl 0679.46012 |
| [22] | Simonovits, M., How to compute the volume in high dimension?, Math. Program., 97, 1, 337-374 (2003) · Zbl 1106.68433 |
| [23] | Vempala, S., Geometric random walks: A survey, (MSRI Volume on Combinatorial and Computational Geometry, vol. 52 (2005), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 577-616 · Zbl 1106.52002 |
| [24] | Vempala, S. S., The Random Projection Method (2004), American Mathematical Society · Zbl 1058.68063 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
