Scott E. Decatur, Oded Goldreich, Dana Ron

In a variety of PAC learning models, a tradeoff between time and

information seems to exist: with unlimited time, a small amount of

information suffices, but with time restrictions, more information

sometimes seems to be required.

In addition, it has long been known that there are

concept classes ...
more >>>

Igor E. Shparlinski

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 >>>

Nir Bitansky

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>>