Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-PSEUDORANDOMNESS, PSEUDORANDOM EXTRACTOR, DERANDOMIZATION, DIMENSION, UNPREDICTABILITY:
Reports tagged with non-pseudorandomness, pseudorandom extractor, derandomization, dimension, unpredictability:
TR14-057 | 17th April 2014
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revisions: 3

In this paper, we propose a quantification of distributions on a set
of strings, in terms of how close to pseudorandom the distribution
is. The quantification is an adaptation of the theory of dimension of
sets of infinite sequences first introduced by Lutz
\cite{Lutz:DISS}.
We show that this definition ... more >>>




ISSN 1433-8092 | Imprint