Computational Randomness from Generalized Hardcore Sets

DOI10.1007/978-3-642-22953-4_7zbMATH Open1342.68172OpenAlexW6156751MaRDI QIDQ3088271FDOQ3088271

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Nonuniform indistinguishability and unpredictability hardcore lemmas: new proofs and applications to pseudoentropy
• Title not available (Why is that?)
• On the Complexity of Hard-Core Set Constructions
• Complexity of hard-core set proofs

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)