Dispersion of mass and the complexity of geometric problems
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/38884 |
| _version_ | 1826189823777439744 |
|---|---|
| author | Rademacher, Luis Alexis |
| author2 | Santosh S. Vempala. |
| author_facet | Santosh S. Vempala. Rademacher, Luis Alexis |
| author_sort | Rademacher, Luis Alexis |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. |
| first_indexed | 2024-09-23T08:23:44Z |
| format | Thesis |
| id | mit-1721.1/38884 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:23:44Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/388842022-01-13T07:54:35Z Dispersion of mass and the complexity of geometric problems Rademacher, Luis Alexis Santosh S. Vempala. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Department of Mathematics Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Includes bibliographical references (p. 71-73). 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 Rn (the current best algorithm has complexity roughly n4, conjectured to be n3). 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. We also consider the problem of computing the centroid of a convex body in Rn. (cont.) We prove that if the body is a polytope given as an intersection of half-spaces, then computing the centroid exactly is #P-hard, even for order polytopes, a special case of 0{1 polytopes. We also prove that if the body is given by a membership oracle, then for any deterministic algorithm that makes a polynomial number of queries there exists a body satisfying a roundedness condition such that the output of the algorithm is outside a ball of radius [sigma]=100 around the centroid, where [sigma]2 is the minimum eigenvalue of the inertia matrix of the body. Finally, we consider the problem of determining whether a given set S in Rn is approximately convex, i.e., if there is a convex set K [mu] Rn such that the volume of their symmetric difference is at most vol(S) for some given . When the set is presented only by a membership oracle and a random oracle, we show that the problem can be solved with high probability using poly(n)(c=²)n oracle calls and computation time. We complement this result with an exponential lower bound for the natural algorithm that tests convexity along random lines. We conjecture that a simple 2-dimensional version of this algorithm has polynomial complexity. by Luis Alexis Rademacher. Ph.D. 2007-09-27T19:30:56Z 2007-09-27T19:30:56Z 2007 2007 Thesis http://hdl.handle.net/1721.1/38884 166275305 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 73 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Rademacher, Luis Alexis Dispersion of mass and the complexity of geometric problems |
| title | Dispersion of mass and the complexity of geometric problems |
| title_full | Dispersion of mass and the complexity of geometric problems |
| title_fullStr | Dispersion of mass and the complexity of geometric problems |
| title_full_unstemmed | Dispersion of mass and the complexity of geometric problems |
| title_short | Dispersion of mass and the complexity of geometric problems |
| title_sort | dispersion of mass and the complexity of geometric problems |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/38884 |
| work_keys_str_mv | AT rademacherluisalexis dispersionofmassandthecomplexityofgeometricproblems |