| bibtype |
J -
Journal Article
|
| ARLID |
0411049 |
| utime |
20240903170614.9 |
| mtime |
20060210235959.9 |
| title
(primary) (eng) |
Kolmogorov complexity, pseudorandom generators and statistical models testing |
| specification |
|
| serial |
| ARLID |
cav_un_epca*0297163 |
| ISSN |
0023-5954 |
| title
|
Kybernetika |
| volume_id |
38 |
| volume |
6 (2002) |
| page_num |
747-759 |
| publisher |
| name |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
|
| keyword |
Kolmogorov complexity |
| keyword |
pseudorandom generators |
| keyword |
statistical models testing |
| author
(primary) |
| ARLID |
cav_un_auth*0101205 |
| name1 |
Šindelář |
| name2 |
Jan |
| institution |
UTIA-B |
| fullinstit |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
| author
|
| ARLID |
cav_un_auth*0101069 |
| name1 |
Boček |
| name2 |
Pavel |
| institution |
UTIA-B |
| full_dept |
Department of Stochastic Informatics |
| fullinstit |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
| COSATI |
12B |
| cas_special |
| project |
| project_id |
GA102/99/1564 |
| agency |
GA ČR |
| ARLID |
cav_un_auth*0004444 |
|
| research |
CEZ:AV0Z1075907 |
| abstract
(eng) |
An attempt to formalize heuristic concepts like strings (sequence resp.) "typical" for a probability measure is stated in the paper. Both generating and testing of such strings is considered. Kolmogorov complexity theory is used as a tool. It is shown that no pseudorandom generator can produce long "typical" strings. The time complexity of pseudorandom generators with oracles capable to recognize "typical" strings is shown to be at least exponential with respect to the length of the output. |
| RIV |
BB |
| department |
SI |
| permalink |
http://hdl.handle.net/11104/0131136 |
| ID_orig |
UTIA-B 20030036 |
| arlyear |
2002 |
| mrcbU63 |
cav_un_epca*0297163 Kybernetika 0023-5954 Roč. 38 č. 6 2002 747 759 Ústav teorie informace a automatizace AV ČR, v. v. i. |
|