CRACS - Indexed Articles in Conferences

Permanent URI for this collection

http://localhost:4000/handle/123456789/124

Browse

Browsing CRACS - Indexed Articles in Conferences by Author "Aaronson,S"
  • Item
    Sophistication as randomness deficiency
    ( 2013) Mota,F ; Aaronson,S ; Luís Filipe Antunes ; Souto,A
    The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness deficiency. Naive sophistication measures the minimum number of bits needed to specify a set in which the string is a typical element. Thanks to Vereshchagin and Vitányi, we know that sophistication and naive sophistication are equivalent up to low order terms. We use this to relate sophistication to lossy compression, and to derive an alternative formulation for busy beaver computational depth. © 2013 Springer-Verlag.