Reconstructive dispersers and hitting set generators

DOI10.1007/s00453-008-9266-zzbMath1194.68116OpenAlexW2180526031MaRDI QIDQ2391190

Christopher Umans

Publication date: 24 July 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.6278

zbMATH Keywords

derandomizationdisperserhitting set generator

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derandomizing Arthur-Merlin games using hitting sets
• Language compression and pseudorandom generators
• Reducing the seed length in the Nisan-Wigderson generator
• Hardness vs randomness
• Decoding of Reed Solomon codes beyond the error-correction bound
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Storing information with extractors.
• Extractors from Reed-Muller codes
• Simplified Derandomization of BPP Using a Hitting Set Generator
• Extractors and pseudo-random generators with optimal seed length
• List decoding algorithms for certain concatenated codes
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Simple extractors for all min-entropies and a new pseudorandom generator
• Extractor Codes
• Better extractors for better codes?
• A new general derandomization method
• Weak Random Sources, Hitting Sets, and BPP Simulations
• Loss-less condensers, unbalanced expanders, and extractors
• Extractors and pseudorandom generators
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Pseudo-random generators for all hardnesses
• Pseudorandom generators without the XOR lemma

This page was built for publication: Reconstructive dispersers and hitting set generators