Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with condenser:
TR05-100 | 30th August 2005
David Zuckerman

Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>

TR11-161 | 4th December 2011
Xin Li

Design Extractors, Non-Malleable Condensers and Privacy Amplification

We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors ... more >>>

ISSN 1433-8092 | Imprint