We define a polynomial threshold function to be a function of
the form f(x) = sgn(p(x)) for p a polynomial. We discuss some
recent techniques for dealing with polynomial threshold functions,
particular when evaluated on random Gaussians. We...
It is well-known that any Boolean function f:{-1,+1}^n \to
{-1,+1} can be written uniquely as a polynomial f(x) = \sum_{S
subset [n]} f_s \prod_{i in S} x_i. The collection of coefficients
(f_S's) this expression are referred to (with good reason)...
I'll talk on work in progress on algebraic and analytic geometry
over the field of one element F_1. This work originates in
non-Archimedean analytic geometry as a result of a search for
appropriate framework for so called skeletons of analytic...
We attach Galois representations to automorphic representations
on unitary groups whose weight (=component at infinity) is a
holomorphic limit of discrete series. The main innovation is a new
construction of congruences, using the Hasse Invariant...
Non-relativization of complexity issues can be interpreted as
giving evidence that these issues cannot be resolved by
“black-box” techniques. We show that the assumption $DistNP
\subseteq AvgP$ does not imply that $NP\subseteq BPP$ by...