In this work we give two new constructions of \epsilon-biased
generators. Our first construction answers an open question of
Dodis and Smith, and our second construction
significantly extends a result of Mossel et al.
In particular we obtain the following results:
1. We construct a family of asymptotically good binary ... more >>>
We give an explicit construction of pseudorandom
generators against low degree polynomials over finite fields. We
show that the sum of 2^d small-biased generators with error
\epsilon^{2^{O(d)}} is a pseudorandom generator against degree d
polynomials with error \epsilon. This gives a generator with seed
length 2^{O(d)} \log{(n/\epsilon)}. Our construction follows ...
more >>>
Let p be a fixed prime number, and N be a large integer.
The 'Inverse Conjecture for the Gowers norm' states that if the "d-th Gowers norm" of a function f:\F_p^N \to \F_p is non-negligible, that is larger than a constant independent of N, then f can be non-trivially ...
more >>>
A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>>
In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>
In this paper, two structural results concerning low degree polynomials over the field \mathbb{F}_2 are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of \mathbb{F}_2^n with dimension \Omega(n^{1/(d-1)}) on which f is constant. This result is shown to be tight. ... more >>>
Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is O(d \log{n} + d 2^d), ... more >>>
A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F_2. We introduce a new technique to prove such correlation bounds with F_2 polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>>
This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of {\cal AC}^0[p]-circuits that compute sums mod~q (for primes q\neq p).
The textbook presentations of the latter result ...
more >>>