Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with condensers:
TR01-036 | 2nd May 2001
Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Extractors from Reed-Muller Codes

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

TR06-003 | 8th January 2006
Joshua Buresh-Oppenheim, Rahul Santhanam

Making Hard Problems Harder

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

TR06-134 | 18th October 2006
Venkatesan Guruswami, Chris Umans, Salil Vadhan

Extractors and condensers from univariate polynomials

Revisions: 1

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

TR10-037 | 8th March 2010
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time ... more >>>

TR16-088 | 1st June 2016
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Explicit two-source extractors for near-logarithmic min-entropy

We explicitly construct extractors for two independent $n$-bit sources of $(\log n)^{1+o(1)}$ min-entropy. Previous constructions required either $\mathrm{polylog}(n)$ min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}.

Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction ... more >>>

TR18-066 | 8th April 2018
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>>

ISSN 1433-8092 | Imprint