Polynomial Space Randomness in Analysis

Abstract

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 ${\mathbb{R}}^n$ to define \textit{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.