We show that a pseudo-random number generator,
introduced recently by M. Naor and O. Reingold,
possess one more attractive and useful property.
Namely, it is proved that for almost all values of parameters it
produces a uniformly distributed sequence.
The proof is based on some recent bounds of exponential
more >>>

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly
at random ... more >>>

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected
uniformly at ... more >>>

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

We study solution sets to systems of generalized linear equations of the following form:
$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,
where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ... more >>>

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

more >>>