Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CONDENSER:
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.

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




ISSN 1433-8092 | Imprint