Dimension, Pseudorandomness and Extraction of Pseudorandomness
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10331835" target="_blank" >RIV/00216208:11320/15:10331835 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.221" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.221</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.221" target="_blank" >10.4230/LIPIcs.FSTTCS.2015.221</a>
Alternative languages
Result language
angličtina
Original language name
Dimension, Pseudorandomness and Extraction of Pseudorandomness
Original language description
In this paper we propose a quantification 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 a distribution is quantitatively equivalent to the notion of dimension we define.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
ISBN
978-3-939897-97-2
ISSN
1868-8969
e-ISSN
—
Number of pages
15
Pages from-to
221-235
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Německo
Event location
Bangalore, India
Event date
Dec 16, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—