Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Agrawal, Manindraa | Chakraborty, Diptarkab | Das, Debaratic | Nandakumar, Satyadevd
Affiliations: [a] Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur-208016, India. manindra@cse.iitk.ac.in; http://www.cse.iitk.ac.in/users/manindra/ | [b] Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur-208016, India. diptarka@cse.iitk.ac.in; http://www.cse.iitk.ac.in/users/diptarka/ | [c] Computer Science Institute of Charles University, Charles University in Prague, Malostranské námesti 25, 118 00 Praha 1, Czech Republic. debaratix710@gmail.com | [d] Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur-208016, India. satyadev@cse.iitk.ac.in; http://www.cse.iitk.ac.in/users/satyadev/
Note: [1] A preliminary version of this paper [1] was accepted in the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16–18, 2015, Bangalore, India.
Abstract: In this paper we propose a quantification of ensemble of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock’s work, we also show that the logarithmic loss incurred by a predictor on an ensemble of distributions is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. Further, we apply our quantification to the following problem. If we know that the dimension of an ensemble of distributions on the set of n-length strings is s∈(0,1], can we extract out O(sn) pseudorandom bits out of the distribution? We show that to construct such extractor, one needs at least Ω(logn) bits of pure randomness. However, it is still open to do the same using O(logn) random bits. We show that deterministic extraction is possible in a special case – analogous to the bit-fixing sources introduced by Chor et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic pseudorandom extractor for this source. By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches O(logn) input bits to produce n output bits such that output distribution has dimension s∈(0,1], implies P=BPP.
Keywords: Pseudorandomness, dimension, unpredictability, pseudoentropy, pseudorandom extractor
DOI: 10.3233/COM-160066
Journal: Computability, vol. 6, no. 3, pp. 277-305, 2017
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl