{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:12Z","timestamp":1777516752033,"version":"3.51.4"},"reference-count":35,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2016,9,6]],"date-time":"2016-09-06T00:00:00Z","timestamp":1473120000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2017,8,7]]},"abstract":"<jats:p>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\u2019s 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.<\/jats:p>\n                  <jats:p>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 [Formula: see text], can we extract out [Formula: see text] pseudorandom bits out of the distribution? We show that to construct such extractor, one needs at least [Formula: see text] bits of pure randomness. However, it is still open to do the same using [Formula: see text] random bits. We show that deterministic extraction is possible in a special case \u2013 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.<\/jats:p>\n                  <jats:p>By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches [Formula: see text] input bits to produce n output bits such that output distribution has dimension [Formula: see text], implies [Formula: see text].<\/jats:p>","DOI":"10.3233\/com-160066","type":"journal-article","created":{"date-parts":[[2016,9,6]],"date-time":"2016-09-06T11:15:58Z","timestamp":1473160558000},"page":"277-305","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Dimension, pseudorandomness and extraction of pseudorandomness"],"prefix":"10.1177","volume":"6","author":[{"given":"Manindra","family":"Agrawal","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur-208016, India. \u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diptarka","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur-208016, India. \u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debarati","family":"Das","sequence":"additional","affiliation":[{"name":"Computer Science Institute of Charles University, Charles University in Prague, Malostransk\u00e9 n\u00e1mesti 25, 118 00 Praha 1, Czech Republic."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satyadev","family":"Nandakumar","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Kanpur, Kanpur-208016, India. \u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2016,9,6]]},"reference":[{"key":"ref001","unstructured":"M.\u00a0Agrawal, D.\u00a0Chakraborty, D.\u00a0Das and S.\u00a0Nandakumar, Dimension, pseudorandomness and extraction of pseudorandomness, in: 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, Bangalore, India, 16\u201318 December 2015, 2015, pp.\u00a0221\u2013235."},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703446912"},{"key":"ref003","unstructured":"K.B.\u00a0Athreya and S.N.\u00a0Lahiri, Measure Theory and Probability Theory, Springer Verlag, 2006."},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, R.\u00a0Shaltiel and A.\u00a0Wigderson, Computational analogues of entropy, in: RANDOM-APPROX, S.\u00a0Arora, K.\u00a0Jansen, J.D.P.\u00a0Rolim and A.\u00a0Sahai, eds, Lecture Notes in Computer Science, Vol.\u00a02764, Springer, 2003, pp.\u00a0200\u2013215.","DOI":"10.1007\/978-3-540-45198-3_18"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"B.\u00a0Chor, O.\u00a0Goldreich, J.\u00a0H\u00e5stad, J.\u00a0Freidmann, S.\u00a0Rudich and R.\u00a0Smolensky, The bit extraction problem or t-resilient functions, 1985.","DOI":"10.1109\/SFCS.1985.55"},{"key":"ref007","unstructured":"T.\u00a0Cover, Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin, Technical Report 12, Stanford University Department of Statistics, 1974."},{"key":"ref008","unstructured":"T.M.\u00a0Cover and J.A.\u00a0Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience, 2006."},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"A.\u00a0Gabizon, R.\u00a0Raz and R.\u00a0Shaltiel, Deterministic extractors for bit-fixing sources by obtaining an independent seed, in: Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy, 17\u201319 October 2004, 2004, pp.\u00a0394\u2013403. doi:10.1109\/FOCS.2004.21.","DOI":"10.1109\/FOCS.2004.21"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, The Foundations of Cryptography \u2013 Volume 1, Basic Techniques, Cambridge University Press, 2001.","DOI":"10.1017\/CBO9780511546891"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, O.\u00a0Reingold and S.P.\u00a0Vadhan, Efficiency improvements in constructing pseudorandom generators from one-way functions, in: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, 2010, pp.\u00a0437\u2013446.","DOI":"10.1145\/1806689.1806750"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00138-5"},{"key":"ref015","unstructured":"J.M.\u00a0Hitchcock, Effective Fractal Dimension Bibliography, 2011, http:\/\/www.cs.uwyo.edu\/~jhitchco\/bib\/dim.shtml (current April, 2011)."},{"key":"ref016","unstructured":"J.M.\u00a0Hitchcock, Resource Bounded Measure \u2013 Bibliography, http:\/\/www.cs.uwyo.edu\/~jhitchco\/bib\/rmb.shtml (current April, 2011)."},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"C.Y.\u00a0Hsiao, C.J.\u00a0Lu and L.\u00a0Reyzin, Conditional computational entropy, or toward separating pseudoentropy from compressibility, in: Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, 20\u201324 May 2007, 2007, pp.\u00a0169\u2013186.","DOI":"10.1007\/978-3-540-72540-4_10"},{"key":"ref018","doi-asserted-by":"crossref","unstructured":"R.\u00a0Impagliazzo and A.\u00a0Wigderson, P = BPP unless E has sub-exponential circuits: Derandomizing the xor lemma (preliminary version), in: Proceedings of the 29th STOC, ACM Press, 1996, pp.\u00a0220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"J.\u00a0Kamp and D.\u00a0Zuckerman, Deterministic extractors for bit-fixing sources and exposure-resilient cryptography, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp.\u00a092\u2013101.","DOI":"10.1109\/SFCS.2003.1238184"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"C.J.\u00a0Lu, O.\u00a0Reingold, S.P.\u00a0Vadhan and A.\u00a0Wigderson, Extractors: Optimal up to constant factors, in: STOC, L.L.\u00a0Larmore and M.X.\u00a0Goemans, eds, ACM, 2003, pp.\u00a0602\u2013611.","DOI":"10.1145\/780542.780630"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"J.H.\u00a0Lutz, Gales and the constructive dimension of individual sequences, in: Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, 2000, pp.\u00a0902\u2013913, Revised as [22]. doi:10.1007\/3-540-45022-X_76.","DOI":"10.1007\/3-540-45022-X_76"},{"key":"ref022","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701417723"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.09.005"},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1546"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"N.\u00a0Nisan and D.\u00a0Zuckerman, More deterministic simulation in logspace, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, 16\u201318 May 1993, 1993, pp.\u00a0235\u2013244.","DOI":"10.1145\/167088.167162"},{"key":"ref028","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"Omer Reingold, L.\u00a0Trevisan and S.\u00a0Vadhan, Pseudorandom walks on regular digraphs and the rl vs. l problem, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201806), 2006, pp.\u00a0457\u2013466.","DOI":"10.1145\/1132516.1132583"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"ref031","first-page":"67","volume":"77","author":"Shaltiel R.","year":"2002","journal-title":"Bulletin of the EATCS"},{"key":"ref032","doi-asserted-by":"crossref","unstructured":"L.\u00a0Trevisan and S.P.\u00a0Vadhan, Extracting randomness from samplable distributions, in: FOCS, IEEE Computer Society, 2000, pp.\u00a032\u201342.","DOI":"10.1109\/SFCS.2000.892063"},{"key":"ref033","doi-asserted-by":"crossref","unstructured":"S.P.\u00a0Vadhan and C.J.\u00a0Zheng, Characterizing pseudoentropy and simplifying pseudorandom generator constructions, in: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, 2012, pp.\u00a0817\u2013836.","DOI":"10.1145\/2213977.2214051"},{"key":"ref034","doi-asserted-by":"crossref","unstructured":"H.\u00a0Vollmer, Introduction to Circuit Complexity \u2013 A Uniform Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, 1999.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"ref035","doi-asserted-by":"crossref","unstructured":"A.C.\u00a0Yao, Theory and application of trapdoor functions, in: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS\u201982, IEEE Computer Society, Washington, DC, USA, 1982, pp.\u00a080\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160066","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-160066","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:54Z","timestamp":1777391994000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-160066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,6]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,7]]}},"alternative-id":["10.3233\/COM-160066"],"URL":"https:\/\/doi.org\/10.3233\/com-160066","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,6]]}}}