Increasing the output length of zero-error dispersers

DOI10.1002/RSA.20359MaRDI QIDQ3119044zbMATH OpenOpenAlexFDO

Authors 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

derandomizationpseudorandomnessextractorsRamsey graphs

Mathematics Subject Classification ID

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

Recommendations

• Increasing the Output Length of Zero-Error Dispersers
• scientific article; zbMATH DE number 4110622
• The design of variable-length coding matrix for improving error correcting output codes
• Invertible zero-error dispersers and defective memory with stuck-at errors
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 3859031
• Optimum Overflow Thresholds in Variable-Length Source Coding Allowing Non-Vanishing Error Probability
• The error probability, entropy, and equivocation when the number of input messages increases
• Critical lengths of error events in convolutional codes

Cites work

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

Cited in

(2)

• Invertible zero-error dispersers and defective memory with stuck-at errors
• Increasing the Output Length of Zero-Error Dispersers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3119044)