Access Restriction

Author Wigderson, Avi ♦ Rao, Anup ♦ O'Donnell, Ryan ♦ Kindler, Guy
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract Foam problems are about how to best partition space into bubbles of minimal surface area. We investigate the case where one unit-volume bubble is required to tile d-dimensional space in a periodic fashion according to the standard, cubical lattice. While a cube requires surface area 2d, we construct such a bubble having surface area very close to that of a sphere; that is, proportional to √d (the minimum possible even without the constraint of being periodic). Our method for constructing this "spherical cube" is inspired by foundational questions in the theory of computation related to the concept of hardness amplification. Our methods give new algorithms for "coordinated discretization" of high-dimensional data points, which have near-optimal noise resistance. We also provide the most efficient known cubical foam in three dimensions.
Description Affiliation: Carnegie Mellon University (O'Donnell, Ryan) || University of Washington (Rao, Anup) || Hebrew University of Jerusalem (Kindler, Guy) || Institute for Advanced Study (Wigderson, Avi)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 55
Issue Number 10
Page Count 8
Starting Page 90
Ending Page 97

Open content in new tab

   Open content in new tab
Source: ACM Digital Library