technical Perspective
A high-Dimensional Surprise
By Rocco A. Servedio
HigH-diMensiOnAl spAce is a counterin-tuitive 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 dimensions—finding a simple
curve to fit data points, computing
the volume of a region—can 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 unexpect-
ed connection between spheres and
cubes and construct a new geometric
object that has some of the most fun-
damental properties of both shapes.
Turning first to cubes, they are the ca-
nonical 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 this—for
example, adding bumps to the top and
carving matching divots into the bot-
tom 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 un-
filled. In higher dimensions spheres
do even worse: the fraction of unfilled
space becomes exponentially larger (as
a function of d) than the fraction actu-
ally 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 shape—small surface
area means less building material and
more uniform water temperature.) In
fact, while a d-dimensional cube of vol-
ume 1 has surface area 2d, a d-dimen-
sional sphere of volume 1 has surface
area only about 4. 13 d, which is much
smaller in high dimensions.
References
1. Choe. J. on the existence and regularity of
fundamental domains with least boundary area. J.
Differential Geom. 29 (1989), 623–663.
2. ran, r. a counterexample to strong parallel
repetition. In Proceedings of the 49th IEEE
Symposium on Foundations of Computer Science
(2008), 369–373.
Rocco Servedio ( rocco@cs.columbia.edu) is an associate
professor of computer science at Columbia university,
new york, ny.