On the notion of infinite pseudorandom sequences

DOI10.1016/0304-3975(86)90081-2zbMath0623.68044OpenAlexW2078472124MaRDI QIDQ1091817

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

zbMATH Keywords

Kolmogorov complexitypolynomial timepolynomial spaceinfinite pseudorandom sequencesMartin-Löf tests

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Information theory (general) (94A15)

Related Items (21)

On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ Compressibility and uniform complexity ⋮ Unnamed Item ⋮ Sub-computable Bounded Pseudorandomness ⋮ On resource-bounded instance complexity ⋮ Pseudorandom sources for BPP ⋮ On characterizations of the class PSPACE/poly ⋮ On unstable and unoptimal prediction ⋮ One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions ⋮ Random languages for nonuniform complexity classes ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Almost everywhere high nonuniform complexity ⋮ Circuit size relative to pseudorandom oracles ⋮ Symmetry of information and one-way functions ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ The structure of logarithmic advice complexity classes ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Resource bounded randomness and computational complexity ⋮ Calibrating Randomness ⋮ An upward measure separation theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Process complexity and effective random tests
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A Simple Unpredictable Pseudo-Random Number Generator
• A Theory of Program Size Formally Identical to Information Theory
• Noncomplex sequences: characterizations and examples
• General random sequences and learnable sequences
• On the Length of Programs for Computing Finite Binary Sequences
• On the size of machines
• On the Length of Programs for Computing Finite Binary Sequences
• Random Sets in Subrecursive Hierarchies
• A variant of the Kolmogorov concept of complexity
• The Literature on von Mises' Kollektivs Revisited
• 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

This page was built for publication: On the notion of infinite pseudorandom sequences