Extracting Computational Entropy and Learning Noisy Linear Functions

DOI10.1007/978-3-642-02882-3_34zbMath1248.68361OpenAlexW2164430266MaRDI QIDQ5323082

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

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02882-3_34

Mathematics Subject Classification ID

Computational learning theory (68Q32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Computational Randomness from Generalized Hardcore Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Randomness is linear in space
• Learning Polynomials with Queries: The Highly Noisy Case
• Extractors for a constant number of polynomially small min-entropy independent sources
• Extracting Randomness from Multiple Independent Sources
• Extractor Codes
• Extractors
• Extractors with weak random seeds
• Deterministic Extractors for Independent-Symbol Sources
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• A Pseudorandom Generator from any One-way Function
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
• Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
• Extractors and pseudorandom generators
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
• Extracting Randomness Using Few Independent Sources
• Deterministic extractors for small-space sources
• Noise-tolerant learning, the parity problem, and the statistical query model
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Simulating independence