Dimension, Pseudorandomness and Extraction of Pseudorandomness
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Dimension, Pseudorandomness and Extraction of Pseudorandomness
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Dimension, Pseudorandomness and Extraction of Pseudorandomness
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
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
—
Počet stran výsledku
15
Strana od-do
221-235
Název nakladatele
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Místo vydání
Dagstuhl, Německo
Místo konání akce
Bangalore, India
Datum konání akce
16. 12. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—