Computational Randomness from Generalized Hardcore Sets
From MaRDI portal
Publication:3088271
DOI10.1007/978-3-642-22953-4_7zbMath1342.68172MaRDI QIDQ3088271
Shi-Chun Tsai, Chia-Jung Lee, Chi-Jen Lu
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
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boosting and hard-core set construction
- Randomness is linear in space
- Learning Polynomials with Queries: The Highly Noisy Case
- On uniform amplification of hardness in NP
- Key agreement from weak bit agreement
- Deterministic Extractors for Independent-Symbol Sources
- The Nonstochastic Multiarmed Bandit Problem
- Extracting Computational Entropy and Learning Noisy Linear Functions
- On the Complexity of Hard-Core Set Constructions
- Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
- Using Nondeterminism to Amplify Hardness
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Hardness amplification within NP
- Pseudorandom generators without the XOR lemma