License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.86
URN: urn:nbn:de:0030-drops-64943
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6494/
Huang, Xiang ;
Stull, Donald M.
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 R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation theorem holds for a point x for every pspace L_1-computable function.
BibTeX - Entry
@InProceedings{huang_et_al:LIPIcs:2016:6494,
author = {Xiang Huang and Donald M. Stull},
title = {{Polynomial Space Randomness in Analysis}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {86:1--86:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6494},
URN = {urn:nbn:de:0030-drops-64943},
doi = {10.4230/LIPIcs.MFCS.2016.86},
annote = {Keywords: algorithmic randomness, computable analysis, resource-bounded randomness, complexity theory}
}
|
Keywords: |
|
algorithmic randomness, computable analysis, resource-bounded randomness, complexity theory |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
