On the notion of infinite pseudorandom sequences
From MaRDI portal
DOI10.1016/0304-3975(86)90081-2zbMATH Open0623.68044OpenAlexW2078472124MaRDI QIDQ1091817FDOQ1091817
Authors: Ker-I Ko 
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90081-2
Recommendations
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Cryptography (94A60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Length of Programs for Computing Finite Binary Sequences
- Process complexity and effective random tests
- A Theory of Program Size Formally Identical to Information Theory
- Complexity oscillations in infinite binary sequences
- 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
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Title not available (Why is that?)
- On the Length of Programs for Computing Finite Binary Sequences
- A variant of the Kolmogorov concept of complexity
- A Simple Unpredictable Pseudo-Random Number Generator
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the size of machines
- The Literature on von Mises' Kollektivs Revisited
- Title not available (Why is that?)
- Noncomplex sequences: characterizations and examples
- General random sequences and learnable sequences
- Random Sets in Subrecursive Hierarchies
Cited In (27)
- Sub-computable bounded pseudorandomness
- Subcomputable Schnorr randomness
- One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
- The structure of logarithmic advice complexity classes
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- On one-way functions and sparse languages
- On unstable and unoptimal prediction
- On characterizations of the class PSPACE/poly
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Compressibility and uniform complexity
- Symmetry of information and one-way functions
- Resource bounded randomness and computational complexity
- Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
- Almost everywhere high nonuniform complexity
- Circuit size relative to pseudorandom oracles
- Calibrating Randomness
- Some consequences of the existnce of pseudorandom generators
- A direct PRF construction from Kolmogorov complexity
- Random languages for nonuniform complexity classes
- In Memoriam: Ker-I Ko (1950–2018)
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- On resource-bounded instance complexity
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- NP-hardness of approximating meta-complexity: a cryptographic approach
- An upward measure separation theorem
- Closure of resource-bounded randomness notions under polynomial-time permutations
- Pseudorandom sources for BPP
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)
