On the notion of infinite pseudorandom sequences
The notion of infinite pseudorandom sequences with respect to polynomial time and polynomial space computability is studied. Three formal definitions of pseudorandom sequences are given, based on the polynomial versions of Martin-Löf tests, Kolmogorov complexity and von Mises's collectives. One of the main results is the study of the polynomial time and polynomial space versions of the Martin-Löf-Levin-Schnorr Theorem which states that an infinite sequence x is Martin-Löf random if and only if it has high monotonic Kolmogorov complexity. The polynomial space version of this theorem is proved, while the polynomial time version is left open with some evidence showing it could be a difficult problem. In order to develop this result, polynomial time/space-bounded Kolmogorov complexity of infinite sequences has also been studied. It is shown that there exists a double exponential time computable sequence which is pseudorandom with respect to polynomial time computability. Similarly to the randomness with respect to recursive computability, von Mises's definition of pseudorandomness is proved to be weaker than the other two definitions, with respect to both polynomial space and polynomial time computability.
- A Simple Unpredictable Pseudo-Random Number Generator
- A Theory of Program Size Formally Identical to Information Theory
- A variant of the Kolmogorov concept of complexity
- Complexity oscillations in infinite binary sequences
- General random sequences and learnable sequences
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 3724342 (Why is no real title available?)
- scientific article; zbMATH DE number 3489016 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3339412 (Why is no real title available?)
- scientific article; zbMATH DE number 3420624 (Why is no real title available?)
- Noncomplex sequences: characterizations and examples
- On the Length of Programs for Computing Finite Binary Sequences
- On the Length of Programs for Computing Finite Binary Sequences
- On the size of machines
- Process complexity and effective random tests
- Random Sets in Subrecursive Hierarchies
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The definition of random sequences
- The Literature on von Mises' Kollektivs Revisited
- On characterizations of the class PSPACE/poly
- Random languages for nonuniform complexity classes
- Almost everywhere high nonuniform complexity
- Circuit size relative to pseudorandom oracles
- The structure of logarithmic advice complexity classes
- On resource-bounded instance complexity
- Resource bounded randomness and computational complexity
- Symmetry of information and one-way functions
- Some consequences of the existnce of pseudorandom generators
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- Pseudorandom sources for BPP
- Compressibility and uniform complexity
- Subcomputable Schnorr randomness
- In Memoriam: Ker-I Ko (1950–2018)
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Closure of resource-bounded randomness notions under polynomial-time permutations
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Calibrating Randomness
- Sub-computable bounded pseudorandomness
- scientific article; zbMATH DE number 558650 (Why is no real title available?)
- On unstable and unoptimal prediction
- One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- On one-way functions and sparse languages
- Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
- A direct PRF construction from Kolmogorov complexity
- On witness encryption and laconic zero-knowledge arguments
- Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
- Gap MCSP is not (Levin) NP-complete in obfustopia
- Search-to-decision reductions for Kolmogorov complexity
- The non-uniform perebor conjecture for time-bounded Kolmogorov complexity is false
- On black-box meta complexity and function inversion
- NP-hardness of approximating meta-complexity: a cryptographic approach
- On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
- Lower bounds for Levin-Kolmogorov complexity
- A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
- SAT reduces to the minimum circuit size problem with a random oracle
- An upward measure separation theorem
This page was built for publication: On the notion of infinite pseudorandom sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091817)
