7 we obtain the relaxed bubble B shown
in Figure 4. We remark that it has slightly wavy faces and
curved edges, and that the vertices have moved according to
t ≈ 0.1814. The surface area of B is slightly less than 5.602,
according to Surface Evolver.
We have given a probabilistic construction of a cubical foam
with near-spherical surface area. The construction uses
ideas that are new to the study of foams, and is inspired by
work on the limits of “hardness amplification” in certain
computational optimization problems. Our construction
gives the first suggestion that in high dimensions, optimal
foams might not be derived from Voronoi cells and may be
quite unlike polyhedra.
We have also given an algorithmic application of our
foam’s construction: a very “noise-resistant” procedure
for rounding off vectors of d real numbers to integers. This
discretization algorithm may not be practical for very large
d, as Algorithm 1 is likely to run for a number of stages
which is exponential in d. An important open problem is
to find a coordinated discretization procedure with similar noise resistance, but taking time that grows only polynomially in d.
Finally, the construction of our cubical foam used randomness in an essential way; randomness is also used in
other efficient high-dimensional constructions of foams
(such as high-dimensional Kelvin foams). Although randomness is clearly required for noise-resistant coordinated
discretization, it is an intriguing question as to whether it is
necessary for the construction of foams, or whether explicit
or derandomized constructions exist.
Subsequent to our work.
17 Alon and Klartag2 gave a
simpler derivation of our cubical foam via Cheeger’s isoperimetric inequality; their analysis also shows that there
exists a fixed parameter h that can be used as Hi throughout Algorithm 1. In other words, a good foam can be
derived from the random translations of a single droplet
of the form
However, it still remains unknown as to how to construct an
explicit “spherical cube.”
We thank N. Alon, K. Ball, H. Cohn, P. D’Ancona,
M. Goresky, J. Håstad, L. Hoffman, J. R. Lee, A. Klivans,
D. Micciancio, V. Milman, O. Regev, and J. Sullivan for
their insights. We thank R. Nelson for his assistance
with raytracing code. Kindler was supported in part by
the Koshland fellowship and by the Binational Science
Foundation (BSF). O’Donnell was supported in part
by NSF grants CCF-0747250 and CCF-0915893, BSF
grant 2008477, and Sloan, Okawa, and von Neumann
fellowships. Rao was supported in part by NSF grant
CCF-1016565 and a Sloan fellowship. Wigderson was supported by NSF grants CCF-0832797 and DMS-0835373.
1. achlioptas, d., naor, a., Peres, y.
rigorous location of phase transitions
in hard optimization problems. Nature
435 (2005), 759–764.
2. alon, n., klartag, b. economical
toric spines via Cheeger’s inequality.
1 (sept. 18, 2009), 101–111.
3. arnold, W.n., lacy, J.s. Permeability
of the cell envelope and osmotic
behavior in Saccharomyces
cerevisiae. J. Bacteriol. 131,
2 (1977) 564–571.
4. arora, s., lund, C., Motwani, r.,
sudan, M., szegedy, M. Proof
verification and the hardness of
approximation problems. J. ACM
45, 3 (1998), 501–555.
5. arora, s., safra, s. Probabilistic
checking of proofs: a new
characterization of np. J. ACM,
45, 1 (1998), 70–122.
6. ball, P. science in culture:
beijing bubbles. Nature 448, 7151
7. brakke, k.a. the surface evolver. Exp.
Math. 1, 2 (1992), 141–165.
8. butler, g. simultaneous packing
and covering in euclidean space.
Proc. London Math. Soc. 3, 4 (1972),
9. Charikar, M., Chekuri, C., goel, a.,
guha, s., Plotkin, s. approximating
a finite metric by a small number of
tree metrics. In Proceedings
of 39th Annual IEEE Symposium
on Foundations of Computing (1998),
10. Choe, J. on the existence and
regularity of fundamental
domains with least boundary
area. J. Differ. Geom. 29 (1989),
11. Feige, u., kindler, g., o’donnell, r.
understanding parallel repetition
requires understanding foams.
In Proceedings of 22nd Annual
IEEE Conference on
Computational Complexity (2007),
12. Frank, F.C., kasper, J.s. Complex
alloy structures regarded as sphere
packings. I. definitions and basic
principles. Acta Cryst. 11, 3 (1958),
13. hales, t. C. the honeycomb
conjecture. Disc. Comp. Geom. 25, 1
Guy Kindler ( firstname.lastname@example.org),
school of Computer science and
engineering, hebrew university of
Anup Rao ( email@example.com),
Computer science and engineering,
university of Washington.
14. hales, t. C. a proof of the kepler
conjecture. Ann. Math. 162, 3 (2005),
15. holenstein, t. Parallel repetition:
simplifications and the no-signaling
case. In Proceedings of 39th ACM
Symposium on Theory of Computing
16. holenstein, t. Parallel repetition:
simplification and the no-signaling
case. Theory of Computing 5,
1 (2009), 141–172.
17. kindler, g., o’donnell, r., rao, a.,
Wigderson, a. spherical cubes and
rounding in high dimensions. In FOCS
(2008), Ieee Computer society,
18. kusner, r., sullivan, J. M. Comparing
the Weaire–Phelan equal-volume
foam to kelvin’s foam. Forma 11,
3 (1996), 233–242.
19. lee, J.r., naor, a. extending
lipschitz functions via random
metric partitions. Invent. Math.
160, 1 (2005), 59–95.
20. nielsen, l.e., landel, r.F. Mechanical
Properties of Polymers and
Composites, 2nd edn, CrC Press,
boca raton, 1993.
21. Plateau, J. statique expÃl’rimentale
et thÃl’oretique des liquides
soumis aux seules forces
22. rao, a. Parallel repetition in
projection games and a concentration
bound. In Proceedings of 40th ACM
Symposium on Theory of Computing
23. raz, r. a parallel repetition theorem.
SIAM J. Comput. 27, 3 (1998),
24. raz, r. a Counterexample to strong
Parallel repetition. Ieee Computer
society, 2008, 369–373.
25. santalo, l. Integral geometry
and geometric Probability, 2nd
edn, Cambridge university Press,
26. thomson, W. on the division of
space with minimum partitional
area. Philos. Mag. 24 (1887),
27. Weaire, d., Phelan, r. a counterexample to kelvin’s conjecture on
minimal surfaces. Phil. Mag. Lett. 69,
2 (1994), 107–110.
Ryan O’Donnell ( firstname.lastname@example.org),
Computer science department, school
of Computer science, Carnegie Mellon
Avi Wigderson ( email@example.com),
school of Mathematics, Institute for