On the Autoreducibility of Random Sequences

DOI10.1137/S0097539702415317MaRDI QIDQ4441893zbMATH OpenFDO

Authors Todd Ebert, Wolfgang Merkle, Heribert Vollmer

Publication date 8 January 2004

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

Full work available at URL https://doi.org/10.1137/S0097539702415317

zbMATH Keywords

density of guessed bitserror-correcting codeshat problemhypercube topologyinfinitely often autoreducibilityMartin-Löf random sequencesp-random sequencesrec-random sequencestruth-table autoreducibilityTuring autoreducibility

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1759420
• scientific article; zbMATH DE number 4047167
• scientific article; zbMATH DE number 3895049
• On the pseudorandomness of automatic sequences
• The asymptotic distribution of elements in automatic sequences
• The structure of random automorphisms of the rational numbers
• Remarks on "Random Sequences"
• scientific article; zbMATH DE number 3971857
• On irregularity theorems for random sequences
• On some transformations of random sequences

Cited in

(16)

• On the pseudorandomness of automatic sequences
• Hat problem: a new strategy based on quantum stabilizer codes
• Hat guessing numbers of degenerate graphs
• Bears with hats and independence polynomials
• scientific article; zbMATH DE number 1497861 (Why is no real title available?)
• scientific article; zbMATH DE number 1759420 (Why is no real title available?)
• Finite dynamical systems, hat games, and coding theory
• scientific article; zbMATH DE number 1929940 (Why is no real title available?)
• scientific article; zbMATH DE number 1929969 (Why is no real title available?)
• New constructions and bounds for Winkler's hat game
• On the construction of effectively random sets
• Derandomization of auctions
• On 1-factorizations of bipartite Kneser graphs
• Bears with hats and independence polynomials
• Ebert's asymmetric three person three color hat game
• The hat guessing number of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4441893)