Increasing the output length of zero-error dispersers

DOI10.1002/RSA.20359zbMath1241.05133OpenAlexW2568131744MaRDI QIDQ3119044

Ariel Gabizon, Ronen Shaltiel

Publication date: 7 March 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20359

zbMATH Keywords

derandomizationRamsey graphspseudorandomnessextractors

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distribution theory (60E99)

Cites Work

• Extractors and rank extractors for polynomial sources
• On the construction of affine extractors
• Generating quasi-random sequences from semi-random sources
• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• Randomness is linear in space
• Deterministic extractors for affine sources over large fields
• Extractors for a constant number of polynomially small min-entropy independent sources
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Kakeya Sets, New Mergers, and Old Extractors
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Extractors
• Extractors with weak random seeds
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Implicit $O(1)$ Probe Search
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
• Extracting Randomness Using Few Independent Sources
• Deterministic extractors for small-space sources
• Simulating independence

This page was built for publication: Increasing the output length of zero-error dispersers