We consider the problem of constructing pseudorandom generators
for read-once circuits. We give an explicit construction of a
pseudorandom generator for the class of read-once constant depth
circuits with unbounded fan-in AND, OR, NOT and...
Shannon's notion of entropy measures the amount of "randomness"
in a process. However, to an algorithm with bounded resources, the
amount of randomness can appear to be very different from the
Shannon entropy. Indeed, various measures of...
I will report on some recent work on multiple zeta values. I
will sketch the definition of motivic multiple zeta values, which
can be viewed as a prototype of a Galois theory for certain
transcendental numbers, and then explain how they were used...
One of the principal questions about L-functions is the size of
their critical values. In this talk, we will present a new
subconvexity bound for the central value of a Dirichlet L-function
of a character to a prime power modulus, which breaks a...
A property of finite graphs is called nondeterministically
testable if it has a "certificate'' such that once the certificate
is specified, its correctness can be verified by random local
testing. In this talk we consider certificates that consist...
A blue mushroom cloud fills the page, its contour traced by the
comet-like tails of shrieking heads whose gaping mouths spew out
furious curses in a rain of profanity over needle-stiff bodies
littering the ground. This lecture by Mignon Nixon...
The goal of the Balanced Separator problem is to find a balanced
cut in a given graph G(V,E), while minimizing the number of edges
that cross the cut. It is a fundamental problem with applications
in clustering, image segmentation, community...
We study the list-decodability of multiplicity codes.
These codes, which are based on evaluations of high-degree
polynomials and their derivatives, have rate approaching 1 while
simultaneously allowing for sublinear-time error-correction. In
this...
Heegaard Floer homology groups were recently introduced by
Ozsvath and Szabo to study properties of 3-manifolds and knots in
them. The definition of the invariants rests on delicate
holomorphic geometry, making the actual computations
cumbersome...
