"a shape that ... lies halfway between a square and a circle" An article in the
Notices of the AMS, Volume 61, Issue 10, 2014
(PDF download link),
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.")
 A: This is work by Guy Kindler, Ryan O’Donnell, Anup Rao, and Avi Wigderson, published in Spherical Cubes and Rounding in High Dimensions (2008), and in Spherical Cubes:
Optimal Foams from Computational Hardness Amplification (2012).


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.

A: Just to supplement Carlo's answer with a figure
that illustrates this intermediate cube-sphere shape in $\mathbb{R}^3$, 
from the 2012 paper
he cites—"we provide the most 
efficient known cubical foam in 3 dimensions":

 


