An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy

DOI10.1137/17M1133245OpenAlexW2988618147MaRDI QIDQ5073519

Dean Doron, Avraham Ben-Aroya, Amnon Ta-Shma

Publication date: 3 May 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1133245

zbMATH Keywords

Ramsey graphscondenserstwo-source extractorsnonmalleable extractors

Mathematics Subject Classification ID

Ramsey theory (05D10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing Ramsey graphs from Boolean function representations
• The influence of large coalitions
• Almost \(k\)-wise independence versus \(k\)-wise independence
• Intersection theorems with geometric consequences
• The Shannon capacity of a union
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Low rank co-diagonal matrices and Ramsey graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A Sample of Samplers: A Computational Perspective on Sampling
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Extractors with weak random seeds
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• A note on constructive methods for ramsey numbers
• Explicit Resilient Functions Matching Ajtai-Linial
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Improved non-malleable extractors, non-malleable codes and independent source extractors
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Two-source dispersers for polylogarithmic entropy and improved ramsey graphs
• Explicit two-source extractors and resilient functions
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• Key Derivation without Entropy Waste
• Extractors for Circuit Sources
• New independent source extractors with exponential improvement
• Extracting Randomness Using Few Independent Sources
• Some remarks on the theory of graphs
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Simulating independence
• Lower bounds for some Ramsey numbers

This page was built for publication: An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy