DocumentCode
2434100
Title
Rarity for Semimeasures
Author
Levin, Leonid A.
fYear
2012
fDate
20-23 Oct. 2012
Firstpage
510
Lastpage
513
Abstract
The notion of Kolmogorov-Martin-Lof Random sequences is extended from computable to enumerable distributions. This allows definitions of various other properties, such as mutual information in infinite sequences. Enumerable distributions (as well as distributions faced in some finite multi-party settings) are semi measures, handling those requires care.
Keywords
computability; computational complexity; random sequences; set theory; statistical distributions; Kolmogorov complexity; Kolmogorov-Martin-Lof random sequences; enumerable distributions; finite multiparty settings; infinite sequences; mutual information; probability distribution; semimeasures; Complexity theory; Computer science; Educational institutions; Lattices; Mutual information; Nickel; Probability distribution; complexity;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
Conference_Location
New Brunswick, NJ
ISSN
0272-5428
Print_ISBN
978-1-4673-4383-1
Type
conf
DOI
10.1109/FOCS.2012.50
Filename
6375329
Link To Document