We show that polynomial-time randomness (p-randomness) is preserved under a variety of familiar operations, including addition and multiplication by a nonzero polynomial-time com-putable real number. These results follow from a general theorem: If I ⊆ R is an open interval, f: I → R is a function, and r ∈ I is p-random, then f(r) is p-random provided 1. f is p-computable on the dyadic rational points in I, and 2. f varies sufficiently at r, i.e., there exists a real constant C> 0 such that either (∀x ∈ I − {r}) f(x) − f(r) x − r ≥
The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary func-tion f: R → ...
Space and time are the fundamental parameters of complexity theory. The thesis of this paper is that...
1 Introduction Recently there has been exciting progress in our understanding of algorithmicrandomne...
We show that a real z is polynomial time random if and only if each nondecreasing polynomial time co...
Abstract. We characterize some major algorithmic randomness no-tions via differentiability of effect...
Abstract. We characterize some major algorithmic randomness no-tions via differentiability of effect...
Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that s...
An infinite bit sequence is called recursively random if no computable strategy betting along the se...
The main result of this paper is a polynomial time version of Rademacher\u27s theorem. We show that ...
We show that polynomial time randomness of a real number does not depend on the choice of a base for...
AbstractFollowing a suggestion of Zvonkin and Levin, we generalize Martin-Löf’s definition of infini...
AbstractThe following is a survey of resource bounded randomness concepts and their relations to eac...
We study the interaction between polynomial space randomness and a fundamental result of analysis, t...
Brattka, Miller and Nies [1] showed that some randomness notions are char-acterized by dierentiabili...
It is known that if x ∈ [0, 1] is polynomial time random (i.e. no polynomial time computable marting...
The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary func-tion f: R → ...
Space and time are the fundamental parameters of complexity theory. The thesis of this paper is that...
1 Introduction Recently there has been exciting progress in our understanding of algorithmicrandomne...
We show that a real z is polynomial time random if and only if each nondecreasing polynomial time co...
Abstract. We characterize some major algorithmic randomness no-tions via differentiability of effect...
Abstract. We characterize some major algorithmic randomness no-tions via differentiability of effect...
Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that s...
An infinite bit sequence is called recursively random if no computable strategy betting along the se...
The main result of this paper is a polynomial time version of Rademacher\u27s theorem. We show that ...
We show that polynomial time randomness of a real number does not depend on the choice of a base for...
AbstractFollowing a suggestion of Zvonkin and Levin, we generalize Martin-Löf’s definition of infini...
AbstractThe following is a survey of resource bounded randomness concepts and their relations to eac...
We study the interaction between polynomial space randomness and a fundamental result of analysis, t...
Brattka, Miller and Nies [1] showed that some randomness notions are char-acterized by dierentiabili...
It is known that if x ∈ [0, 1] is polynomial time random (i.e. no polynomial time computable marting...
The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary func-tion f: R → ...
Space and time are the fundamental parameters of complexity theory. The thesis of this paper is that...
1 Introduction Recently there has been exciting progress in our understanding of algorithmicrandomne...