BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/545
DTSTAMP:20230914T125928Z
SUMMARY:Tiling ${\\mathbb R}^d$ via Spherical Cubes
DESCRIPTION:Speaker: Prahladh Harsha\n\nAbstract: \nAbstract: Consider th
e following question: what is the least surface area of a unit volume body
that tiles the d-dimensional space under translations by ${\\mathbb Z}^d$
? The answer is at most $2d$ as the cube tiles ${\\mathbb R}^d$ and at lea
st $\\sqrt{2\\pi e}\\cdot \\sqrt{d}$ since amongst all unit volume bodies
the sphere has the least surface area. Surprisingly\, the answer to this q
uestion is $O(\\sqrt{d})$\, in other words\, there is a body that is like
the cube\, in that it tiles ${\\mathbb R}^d$ and yet closer to the sphere
with respect to surface area. More surprisingly\, the construction of this
body was inspired by questions in the theory of computational complexity
related to hardness amplification\, in particular\, in attempts to prove K
hot's "unique games conjecture". In this talk\, I'll sketch this construct
ion\, explaining the connection to the unique games conjecture and paralle
l repetition theorem. No prior knowledge of computation complexity will be
assumed.\n\nRef: G. Kindler\, A. Rao\, Ryan O'Donnell\, A. Wigderson Sphe
rical Cubes: Optimal Foams from Computational Hardness Amplification Commu
nications of the ACM\, vol. 55\, no. 10\, pp. 90-97\, 2012.\n\nhttp://dx.d
oi.org/10.1145/2347736.2347757\n
URL:https://www.tcs.tifr.res.in/web/events/545
DTSTART;TZID=Asia/Kolkata:20141028T143000
DTEND;TZID=Asia/Kolkata:20141028T153000
LOCATION:AG-77
END:VEVENT
END:VCALENDAR