Computational Randomness from Generalized Hardcore Sets

DOI10.1007/978-3-642-22953-4_7MaRDI QIDQ3088271zbMATH OpenOpenAlexFDO

Authors Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai

Publication date 19 August 2011

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22953-4_7

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1789922
• On random hard sets for NP
• scientific article; zbMATH DE number 1555920
• Randomness extraction in computability theory
• scientific article; zbMATH DE number 2081094
• Computable Measure Theory and Algorithmic Randomness
• The complexity of constructing pseudorandom generators from hard functions
• Derandomization from Algebraic Hardness
• On elementary computability-theoretic properties of algorithmic randomness
• scientific article; zbMATH DE number 1531917

Cites work

• scientific article; zbMATH DE number 1820017 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• Boosting and hard-core set construction
• Computational analogues of entropy
• Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
• Deterministic Extractors for Independent-Symbol Sources
• Extracting Computational Entropy and Learning Noisy Linear Functions
• Hardness amplification within NP
• Key agreement from weak bit agreement
• Learning polynomials with queries: The highly noisy case
• On the Complexity of Hard-Core Set Constructions
• On uniform amplification of hardness in NP
• Pseudorandom generators without the XOR lemma
• Randomness is linear in space
• The Nonstochastic Multiarmed Bandit Problem
• Using Nondeterminism to Amplify Hardness

Cited in

(4)

• Nonuniform indistinguishability and unpredictability hardcore lemmas: new proofs and applications to pseudoentropy
• scientific article; zbMATH DE number 7150624 (Why is no real title available?)
• Complexity of hard-core set proofs
• On the Complexity of Hard-Core Set Constructions

This page was built for publication: Computational Randomness from Generalized Hardcore Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088271)