Sign In

Communications of the ACM

Research highlights

Technical Perspective: A High-Dimensional Surprise


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook

High-dimensional space is a counterintuitive place, where natural geometric intuitions from the familiar three-dimensional world may lead us badly astray. As a simple example consider the Earth, which has a radius of about 3,950 miles (let's pretend it is a perfect sphere). What fraction of the Earth's surface lies within 1/100 of its radius, that is, within 39.5 miles, from the equator? A reasonable guess would be "about 1/100," and that is almost exactly correct. Now let's think high-dimensionally: what fraction of the surface of a d-dimensional sphere lies within 1/100 of its radius from its equator? Again one might guess "about 1/100," but this is wildly incorrect: all but an exponentially small (in terms of d) fraction of the d-dimensional sphere's surface lies within 1/100 of its radius from the equator. Strange as it seems, virtually all the real estate on d-dimensional Earth is in the tropics!

The challenges of dealing with high-dimensional space are familiar to researchers in fields like machine learning and combinatorial optimization, where the "curse of dimensionality" arises often. Tasks that are easy in few dimensionsfinding a simple curve to fit data points, computing the volume of a regioncan become frustratingly difficult or even provably intractable (assuming P!=NP) in high-dimensional space. Yet sometimes the tables are turned, and things that seem difficult or impossible based on our low-dimensional intuition can, near-magically, become possible in high dimension. The following paper describes such a situation, where a clever construction inspired by ideas from computational complexity theory proves the existence of what seems like a too-good-to-be-true high-dimensional object.

The authors reveal an unexpected connection between spheres and cubes and construct a new geometric object that has some of the most fundamental properties of both shapes. Turning first to cubes, they are the canonical shape that can be used to "tile space" according to a regular grid-like lattice leaving no holes or unfilled space (think of slicing a block of cheese into cubes). Of course a simple cube is not the only shape that can do thisfor example, adding bumps to the top and carving matching divots into the bottom of a cube yields a different, Lego-like shape that also fits perfectly with itself to fill space with no holes under a grid-like tiling. Any shape that can do this is called a "cubical tile."

A sphere is certainly not a cubical tile, since a grid-like pattern of 3D spheres leaves a lot of empty space unfilled. In higher dimensions spheres do even worse: the fraction of unfilled space becomes exponentially larger (as a function of d) than the fraction actually filled by the spheres. But spheres reign supreme for a different property: they have the smallest surface-area-to-volume ratio of any shape, in three or any number of dimensions. (This is one reason why water towers have their familiar round shapesmall surface area means less building material and more uniform water temperature.) In fact, while a d-dimensional cube of volume 1 has surface area 2d, a d-dimensional sphere of volume 1 has surface area only about 4.13cacm5510_a.gif, which is much smaller in high dimensions.

So cubes can tile space perfectly but have high surface-area-to-volume ratio, while spheres have the lowest possible surface-area-to-volume ratio but cannot tile space. The authors show that in high-dimensional space it is possible to get the best of both worlds, by proving that there exists a d-dimensional "spherical cube." This counterintuitive object is a cubical tile (that is, a shape that tiles space perfectly like the cube), but has surface-area-to-volume ratio very nearly as small as that of the sphere: roughly 12.6cacm5510_a.gif, that is, the same as the sphere up to a small constant factor!

Why should we care? There are at least three reasons. First, as described in the paper, their geometric construction yields a highly noise-resistant randomized procedure for rounding high-dimensional data points to integer values; such a procedure could be useful in many scenarios. Second, the authors also obtain the best surface-area-to-volume ratio of any 3D cubical tile, improving on a construction of Choe1 from 1989; this could have practical consequences in material science, fabrication, or related areas. Third, their work is based on a surprising connection to recent deep results on hardness amplification in computational complexity theory;2 their article provides a fascinating perspective on this area, and a great illustration of how ideas from one branch of mathematics can have unexpected yet tremendous utility in a completely different area. Finally, there is the sheer "wow, I wouldn't have thought that's possible!" factorit is just plain neat that you can have a "spherical cube" in high dimensions.

Many important questions remain unanswered, both in the complexity-theoretic foundations of Kindler et al.'s result and in the specifics of their geometric construction. A randomized algorithm, not a particularly efficient one, constructs their cubical tile; natural goals are to come up with a more efficient randomized construction, or ideally even an explicit construction that does not use randomness. We can reasonably hope that future workperhaps again informed by perspectives and ideas from complexity theorywill provide more insights into the mysteries and surprises of high-dimensional geometry.

Back to Top

References

1. Choe. J. On the existence and regularity of fundamental domains with least boundary area. J. Differential Geom. 29 (1989), 623663.

2. Ran, R. A counterexample to strong parallel repetition. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (2008), 369373.

Back to Top

Author

Rocco Servedio (rocco@cs.columbia.edu) is an associate professor of computer science at Columbia University, New York, NY.


©2012 ACM  0001-0782/12/10  $15.00

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • Article
  • References
  • Author