Recently Added

Geometry and arithmetic of sphere packings

Alex Kontorovich
Rutgers University
October 23, 2017
We introduce the notion of a "crystallographic sphere packing," which generalizes the classical Apollonian circle packing. Tools from arithmetic groups, hyperbolic geometry, and dynamics are used to show that, on one hand, there is an infinite zoo of such objects, while on the other, there are essentially finitely many of these, in all dimensions. No familiarity with any of these topics will be assumed.

A nearly optimal lower bound on the approximate degree of AC$^0$

Mark Bun
Princeton University
October 23, 2017

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. For any constant $\delta > 0$, we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves over the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi, and nearly matches the trivial upper bound of $n$ that holds for any function.