Organizers: Laszlo Lovasz, Balazs Szegedy, Kati Vesztergombi and Avi Wigderson
One of the unexpecting emerging interactions between seemingly
distant areas in mathematics is between graph theory and analysis.
One such link is the theory of continuous limits of discrete
structures. This theory has applications in computer...
One powerful theme in complexity theory and pseudorandomness in
the past few decades has been the use of lower bounds to give
pseudorandom generators (PRGs). However, the general results using
this hardness vs. randomness paradigm suffer a...
Gowers' uniformity norms are defined by average of a function
over specific sets of linear forms. We study norms that are
similarly defined by a system of linear forms. We prove that for
bounded complex functions over $F_p^n$, each such norm is...
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...