An article in the
*Notices of the AMS*, Volume 61, Issue 10, 2014
([PDF download link](http://www.ams.org/notices/201410/rnoti-p1240.pdf)),
on Khot's Unique Games Conjecture, says this:



> 
> Another group ... found a 
>  shape that in a certain sense lies halfway between 
>  a square and a circle (though in many more than 
>  two dimensions). 
>  Like a square, copies can be placed next to 
>  each other horizontally and vertically to fill a 
>  whole space without gaps or overlaps, forming a 
>  multi-dimensional foam. But its perimeter is much 
>  smaller than a square—it’s closer to that of a circle, 
>  the object which has the smallest perimeter for the 
>  area contained.
> 
> 
> 


Could someone please either explain this enigmatic description further,
or provide a reference to the original work? Thanks!


(This issue is related to my earlier [answered] question,
"[Optimal planar net for catching convex shapes](https://mathoverflow.net/q/185856/6094).")



"a shape that ... lies halfway between a square and a circle"
This is work by Guy Kindler, Ryan O’Donnell, Anup Rao, and Avi Wigderson, published in [Spherical Cubes and Rounding in High Dimensions](http://www.cs.cmu.edu/~odonnell/papers/spherical-cubes-conference.pdf) (2008), and in [Spherical Cubes:
Optimal Foams from Computational Hardness Amplification](http://www.cs.cmu.edu/~odonnell/papers/spherical-cubes-journal.pdf) (2012).


![](https://ilorentz.org/beenakker/MO/spherical_cube.jpg)



> 
> Foam problems are concerned with how one can partition space into
>  "bubbles" which minimize 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; i.e., proportional to
>  $\sqrt d$ (the minimum possible even without the periodicity
>  constraint). Our method for constructing this "spherical cube" has a
>  surprising inspiration: foundational questions in the theory of
>  computation—specifically the issue of "hardness amplification". We
>  additionally show an algorithmic application of our new foam: a method
>  for "coordinated discretization" of high-dimensional data points which
>  has near-optimal resistance to noise. Finally, we provide the most
>  efficient known cubical foam in 3 dimensions.
> 
> 
> 


