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}...
Invariant theory studies the actions of groups on vector spaces and
what polynomial functions remain invariant under these actions. An
important object related to a group action is the null cone, which
is the set of common zeroes of all homogeneous...
Arithmetic complexity is considered (for many good reasons)
simpler to understand than Boolean complexity. And indeed, we seem
to have significantly more lower bound techniques and results in
arithmetic complexity than in Boolean complexity. Despite...
I will survey some elementary (to state!) problems on groups,
matrices, and tensors, and discuss their motivations arising from
several major problems in computational complexity theory. On each
problem there was some exciting recent progress which...
This paper proves the first super-logarithmic lower bounds on
the cell-probe complexity of dynamic boolean (a.k.a. decision) data
structure problems, a long-standing milestone in data structure
lower bounds.
Communication complexity studies the minimal amount of
information two parties need to exchange to compute a joint
function of their inputs. Results, especially lower bounds in this
basic model found applications in many other areas of
computer...
One of the great mysteries in computational condensed matter
physics is the remarkable practical success of the Density Matrix
Renormalization Group (DMRG) algorithm, since its invention a
quarter century ago, for finding low energy states of 1D...
In his 2005 paper "The Gromov-Witten potential associated to a
TCFT" Kevin Costello described a procedure for recovering an
analogue of the Gromov-Witten potential directly out of a cyclic
A-inifinity algebra or category. Applying his construction...
I will discuss methods for deriving bounds on the roots of
polynomials, and how one can use such bounds to assert the
existence of combinatorial structures with certain spectral
properties. This will include introducing the "method of
interlacing...
We present a polynomial-time algorithm that, given samples from the
unknown valuation distribution of each bidder, learns an auction
that approximately maximizes the auctioneer's revenue in a variety
of single-parameter auction environments...