On the Autoreducibility of Random Sequences

DOI10.1137/S0097539702415317zbMath1032.03036MaRDI QIDQ4441893

Wolfgang Merkle, Todd Ebert, Heribert Vollmer

Publication date: 8 January 2004

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

error-correcting codeshat problemMartin-Löf random sequenceshypercube topologydensity of guessed bitsinfinitely often autoreducibilityp-random sequencesrec-random sequencestruth-table autoreducibilityTuring autoreducibility

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Probabilistic games; gambling (91A60) Turing machines and related notions (03D10)

Related Items (9)

On the construction of effectively random sets ⋮ Finite Dynamical Systems, Hat Games, and Coding Theory ⋮ Bears with hats and independence polynomials ⋮ Hat guessing numbers of degenerate graphs ⋮ Derandomization of auctions ⋮ On 1-factorizations of bipartite Kneser graphs ⋮ The hat guessing number of graphs ⋮ New Constructions and Bounds for Winkler's Hat Game ⋮ Hat problem: a new strategy based on quantum stabilizer codes

This page was built for publication: On the Autoreducibility of Random Sequences