2015/09/29 by Xiang Huang, Huang, Xiang, D. M. Stull +1
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Numerical Methods and Algorithms #cs.CC
paper · pdf · doi:10.48550/arxiv.1509.08825
openalex publication_date 2015/09/29 · arxiv created 2016/04/26 · arxiv updated 2016/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the interaction between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in ℝn to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem holds for every weakly pspace-random point.