Loss-less condensers, unbalanced expanders, and extractors

DOI10.1145/380752.380790zbMath1323.68263OpenAlexW1992499648WikidataQ62398494 ScholiaQ62398494MaRDI QIDQ5175962

Christopher Umans, Amnon Ta-Shma, David Zuckerman

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (14)

On the complexity of approximating the VC dimension. ⋮ Reconstructive dispersers and hitting set generators ⋮ Leader election in ad hoc radio networks: a keen ear helps ⋮ Restrained medium access control on adversarial shared channels ⋮ Meeting the deadline: on the complexity of fault-tolerant continuous gossip ⋮ Coordination Problems in Ad Hoc Radio Networks ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ Rainbow paths ⋮ Extractors from Reed-Muller codes ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Non-interactive timestamping in the bounded-storage model ⋮ Multicast Routing and Design of Sparse Connectors ⋮ Better short-seed quantum-proof extractors ⋮ Storing information with extractors.

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Loss-less condensers, unbalanced expanders, and extractors