Revision #1 Authors: Venkatesan Guruswami, Chris Umans, Salil Vadhan

Accepted on: 13th June 2008 00:00

Downloads: 2887

Keywords:

We give an improved explicit construction of highly

unbalanced bipartite expander graphs with expansion arbitrarily

close to the degree (which is polylogarithmic in the number of

vertices). Both the degree and the number of right-hand vertices

are polynomially close to optimal, whereas the previous

constructions of Ta-Shma, Umans, and Zuckerman (STOC `01) required

at least one of these to be quasipolynomial in the optimal. Our

expanders have a short and self-contained description and analysis,

based on the ideas underlying the recent list-decodable

error-correcting codes of Parvaresh and Vardy (FOCS `05).

Our expanders can be interpreted as near-optimal ``randomness

condensers,'' that reduce the task of extracting randomness from

sources of arbitrary min-entropy rate to extracting randomness from

sources of min-entropy rate arbitrarily close to 1, which is a much

easier task. Using this connection, we obtain a new, self-contained

construction of randomness extractors that is optimal up to constant

factors, while being much simpler than the previous construction of Lu

et al. (STOC `03) and improving upon it when the error parameter is

small (e.g. 1/poly(n)).

TR06-134 Authors: Venkatesan Guruswami, Chris Umans, Salil Vadhan

Publication: 20th October 2006 02:46

Downloads: 2402

Keywords:

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 a constant factor in one parameter only at the expense of a polynomial loss in the other.

Our constructions are based on the Parvaresh-Vardy codes [PV05], and our proof technique is inspired by the list-decoding algorithm for those codes. The main object we construct is a condenser that loses only the entropy of its seed plus one bit, while condensing to entropy rate $1 - \alpha$ for any desired constant $\alpha > 0$. This construction is simple to describe, and has a short and completely self-contained analysis. Our other results only require, in addition, standard uses of randomness-efficient hash functions (to obtain a lossless condenser) or expander walks (to obtain an extractor).

Our techniques also show for the first time that a natural construction based on univariate polynomials (i.e., Reed-Solomon codes) yields a condenser that retains a $1 - \alpha$ fraction of the source min-entropy, for any desired constant $\alpha > 0$, while condensing to constant entropy rate and using a seed length that is optimal to within constant factors.