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...
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...
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...
We present an iterative approach to constructing pseudorandom
generators, based on the repeated application of mild pseudorandom
restrictions. We use this template to construct pseudorandom
generators for combinatorial rectangles and read-once...
We study a new type of proof system, where an unbounded prover
and a polynomial time verifier interact, on inputs a string $x$ and
a function $f$, so that the Verifier may learn $f(x)$. The novelty
of our setting is that there no longer are ``good...
A basic fact of algebraic graph theory is that the number of
connected components in an undirected graph is equal to the
multiplicity of the eigenvalue zero in the Laplacian matrix of the
graph. In particular, the graph is disconnected if and only...
