An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy

DOI10.1145/3055399.3055423zbMath1370.68082OpenAlexW2624817146WikidataQ62398441 ScholiaQ62398441MaRDI QIDQ4978057

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

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3055399.3055423

zbMATH Keywords

Ramsey graphscondenserstwo-source extractorsnon-malleable extractors

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Generalized Ramsey theory (05C55) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (14)

Improved computational extractors and their applications ⋮ Extractors: low entropy requirements colliding with non-malleability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Low error efficient computational extractors in the CRS model ⋮ Unnamed Item ⋮ Multi-source non-malleable extractors and applications ⋮ Explicit two-source extractors and resilient functions ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ Lower bounds for matrix factorization

This page was built for publication: An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy