{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T01:17:23Z","timestamp":1767835043961,"version":"3.49.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"10","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0747250CCF-0915893CCF-1016565CCF-0832797DMS-0835373"],"award-info":[{"award-number":["CCF-0747250CCF-0915893CCF-1016565CCF-0832797DMS-0835373"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2008477"],"award-info":[{"award-number":["2008477"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["CCF-0747250CCF-0915893CCF-1016565CCF-0832797DMS-0835373"],"award-info":[{"award-number":["CCF-0747250CCF-0915893CCF-1016565CCF-0832797DMS-0835373"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>\n            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\n            <jats:italic>d<\/jats:italic>\n            -dimensional space in a periodic fashion according to the standard, cubical lattice. While a cube requires surface area 2\n            <jats:italic>d<\/jats:italic>\n            , we construct such a bubble having surface area very close to that of a sphere; that is, proportional to \u221ad (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.\n          <\/jats:p>","DOI":"10.1145\/2347736.2347757","type":"journal-article","created":{"date-parts":[[2012,9,25]],"date-time":"2012-09-25T23:48:08Z","timestamp":1348616888000},"page":"90-97","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Spherical cubes"],"prefix":"10.1145","volume":"55","author":[{"given":"Guy","family":"Kindler","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem"}]},{"given":"Anup","family":"Rao","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Ryan","family":"O'Donnell","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study"}]}],"member":"320","published-online":{"date-parts":[[2012,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03602"},{"key":"e_1_2_1_2_1","volume-title":"Economical toric spines via Cheeger's inequality. 1 (Sept. 18","author":"Alon N.","year":"2009","unstructured":"Alon , N. , Klartag , B. Economical toric spines via Cheeger's inequality. 1 (Sept. 18 , 2009 ), 101--111. Alon, N., Klartag, B. Economical toric spines via Cheeger's inequality. 1 (Sept. 18, 2009), 101--111."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1128\/JB.131.2.564-571.1977"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_6_1","volume-title":"Science in culture: Beijing bubbles. Nature 448, 7151","author":"Ball P.","year":"2007","unstructured":"Ball , P. Science in culture: Beijing bubbles. Nature 448, 7151 ( 2007 ), 256. Ball, P. Science in culture: Beijing bubbles. Nature 448, 7151 (2007), 256."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1992.10504253"},{"key":"e_1_2_1_8_1","first-page":"4","article-title":"Simultaneous packing and covering in Euclidean space","volume":"3","author":"Butler G","year":"1972","unstructured":"Butler , G . Simultaneous packing and covering in Euclidean space . Proc. London Math. Soc. 3 , 4 ( 1972 ), 721--735. Butler, G. Simultaneous packing and covering in Euclidean space. Proc. London Math. Soc. 3, 4 (1972), 721--735.","journal-title":"Proc. London Math. Soc."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796406"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214443065"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.39"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1107\/S0365110X58000487"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010071"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1065"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250852"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a008"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.50"},{"key":"e_1_2_1_18_1","first-page":"3","article-title":"Comparing the Weaire--Phelan equal-volume foam to Kelvin's foam","volume":"11","author":"Kusner R.","year":"1996","unstructured":"Kusner , R. , Sullivan , J.M . Comparing the Weaire--Phelan equal-volume foam to Kelvin's foam . Forma 11 , 3 ( 1996 ), 233--242. Kusner, R., Sullivan, J.M. Comparing the Weaire--Phelan equal-volume foam to Kelvin's foam. Forma 11, 3 (1996), 233--242.","journal-title":"Forma"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"e_1_2_1_20_1","volume-title":"Mechanical Properties of Polymers and Composites","author":"Nielsen L.E.","year":"1993","unstructured":"Nielsen , L.E. , Landel , R.F. Mechanical Properties of Polymers and Composites , 2 nd edn, CRC Press , Boca Raton , 1993 . Nielsen, L.E., Landel, R.F. Mechanical Properties of Polymers and Composites, 2nd edn, CRC Press, Boca Raton, 1993.","edition":"2"},{"key":"e_1_2_1_21_1","volume-title":"Gauthier-villars","author":"Plateau J.","year":"1873","unstructured":"Plateau , J. Statique exp\u00c3l'rimentale et th\u00c3l'oretique des liquides soumis aux seules forces mol\u00c3l'culaires , Gauthier-villars , Paris , 1873 . Plateau, J. Statique exp\u00c3l'rimentale et th\u00c3l'oretique des liquides soumis aux seules forces mol\u00c3l'culaires, Gauthier-villars, Paris, 1873."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374378"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.49"},{"key":"e_1_2_1_25_1","volume-title":"Integral Geometry and Geometric Probability","author":"Santalo L.","year":"2002","unstructured":"Santalo , L. Integral Geometry and Geometric Probability , 2 nd edn, Cambridge University Press , Cambridge , 2002 . Santalo, L. Integral Geometry and Geometric Probability, 2nd edn, Cambridge University Press, Cambridge, 2002.","edition":"2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786448708628135"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/09500839408241577"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2347736.2347757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2347736.2347757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:58Z","timestamp":1750244758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2347736.2347757"}},"subtitle":["optimal foams from computational hardness amplification"],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2347736.2347757"],"URL":"https:\/\/doi.org\/10.1145\/2347736.2347757","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2012-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}