Notions of robust information coding

2014/06/11 by Damir D. Dzhafarov, Damir Dzhafarov, Dzhafarov, Damir +2
Computer Science · Mathematics · #Algorithms and Data Compression #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #math.LO

paper · pdf · doi:10.48550/arxiv.1406.2982

arxiv created 2014/06/11 · arxiv updated 2014/06/12

Abstract

We introduce and study several notions of computability-theoretic reducibility between subsets of ω that are "robust" in the sense that if only partial information is available about the oracle, then partial information can be recovered about the output. These are motivated by reductions between Π¹₂ principles in the context of reverse mathematics, and also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp (2012).

Related

• Comparing Notions of Dense Computability on ω^ω and 2^ω
• The Power of Self-Reducibility: Selectivity, Information, and\n Approximation
• Coarse Reducibility and Algorithmic Randomness
• Redundancy as a Structural Information Principle for Learning and Generalization
• Irreducibility is Minimum Synergy Among Parts