On the notion of infinite pseudorandom sequences

DOI10.1016/0304-3975(86)90081-2MaRDI QIDQ1091817zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

infinite pseudorandom sequencesKolmogorov complexityMartin-Löf testspolynomial spacepolynomial time

Mathematics Subject Classification ID

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

Cites work

• 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

Cited in

(39)

• 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)