A hardness of approximation result in metric geometry
- PDF / 358,365 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 220 Views
Selecta Mathematica New Series
A hardness of approximation result in metric geometry Zarathustra Brady1 · Larry Guth1 · Fedor Manin2
© Springer Nature Switzerland AG 2020
Abstract We show that it is NP-hard to approximate the hyperspherical radius of a triangulated manifold up to an almost-polynomial factor. Keywords Hyperspherical radius · Hardness of approximation Mathematics Subject Classification 53C23 · 68Q17
1 Introduction This paper is concerned with the problem of estimating the smallest Lipschitz constant of a map with a given degree. We consider this problem from the point of view of computational complexity. Suppose that is a closed oriented triangulated manifold of dimension n. We equip with a metric by making each simplex a unit equilateral Euclidean simplex. We let L =0 () and L 1 () denote the smallest Lipschitz constant of a map from to the unit n-sphere with non-zero degree and with degree 1, repsectively. When is a triangulated 2-sphere, the paper [14] gives a polynomial time algorithm to estimate L =0 () up to a constant factor. In contrast, if is a triangulated surface of arbitrary degree, we show that it is NP-hard to approximate L =0 () up to a constant factor, or indeed to within a far wider range. Similarly, if n ≥ 3 and is a triangulation of
B
Fedor Manin [email protected] Zarathustra Brady [email protected]; [email protected] Larry Guth [email protected]
1
Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139-7307, USA
2
University of California, Santa Barbara, CA 93106, USA 0123456789().: V,-vol
54
Page 2 of 20
Z. Brady et al.
S n , then we show that it is NP-hard to estimate L =0 (). Here is a more precise and general statement. Theorem 1.1 Let n ≥ 2. For a triangulation of S n (if n ≥ 3) or a triangulated surface (if n = 2), both L =0 () and L 1 () are NP-hard to approximate to within N c/ log log N , where N = vol and c > 0 depends on n. Compare the total range of possible values for these quantities. The “roundest” possible shape for is approximately a round n-sphere of radius N 1/n , and in the worst case one can contract all but a single simplex. Therefore, N −1/n L =0 () L 1 () 1. Background In the 1970s Gromov began to investigate the smallest Lipschitz constant of a map in a given homotopy class [11]. For instance, he showed that the smallest Lipschitz constant of a degree D map from the unit n-sphere to itself is ∼ D 1/n . In [13], Gromov and Lawson defined the hyperspherical radius of a (closed oriented) Riemannian n-manifold ( n , g) as the largest radius R so that ( n , g) admits a 1-Lipschitz map to the round n-sphere of radius R with non-zero degree. The hyperspherical radius of is 1/L =0 (). Gromov and Lawson proved that if the scalar curvature of g is at least 1, and is spin, then the hyperspherical radius of ( n , g) is at most a constant C(n). The most well-known open problem about hyperspherical radius involves the universal covers of aspherical manifolds. Suppose that is a closed
Data Loading...
