Surface Evolver, 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.

5. DiSCuSSion

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.”

Acknowledgments

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.

References

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 (2007), 256.

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), 721–735.

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), 379–388.

10. Choe, J. on the existence and regularity of fundamental domains with least boundary area. J. Differ. Geom. 29 (1989), 623–663.

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), 179–192.

12. Frank, F.C., kasper, J.s. Complex alloy structures regarded as sphere packings. I. definitions and basic principles. Acta Cryst. 11, 3 (1958), 184–190.

13. hales, t. C. the honeycomb conjecture. Disc. Comp. Geom. 25, 1 (2001), 1–22.

Guy Kindler ( [e-mail]), school of Computer science and engineering, hebrew university of Jerusalem.

Anup Rao ( [e-mail]), Computer science and engineering, university of Washington.

14. hales, t. C. a proof of the kepler conjecture. Ann. Math. 162, 3 (2005), 1065–1186.

15. holenstein, t. Parallel repetition: simplifications and the no-signaling case. In Proceedings of 39th ACM Symposium on Theory of Computing (2007), 411–419.

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, 189–198.

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 molÃl’culaires, gauthier-villars, Paris, 1873.

22. rao, a. Parallel repetition in projection games and a concentration bound. In Proceedings of 40th ACM Symposium on Theory of Computing (2008), 1–10.

23. raz, r. a parallel repetition theorem. SIAM J. Comput. 27, 3 (1998), 763–803.

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, Cambridge, 2002.

26. thomson, W. on the division of space with minimum partitional area. Philos. Mag. 24 (1887), 503–514.

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 ( [e-mail]), Computer science department, school of Computer science, Carnegie Mellon university.

Avi Wigderson ( [e-mail]), school of Mathematics, Institute for advanced study.