### Revision(s):

__
Revision #2 to TR04-069 | 5th February 2006 00:00
__
#### Improving the Alphabet Size in Expander Based Code Constructions

**Abstract:**
Various code constructions use expander graphs to improve the

error resilience. Often the use of expanding graphs comes at the

expense of the alphabet size. This is the case, e.g., in

\cite{abnnr}, \cite{guruswami01expanderbased} and \cite{Guru04}.

We show that by replacing the balanced expanding graphs used in

the above constructions with unbalanced dispersers or extractors

depending on the actual construction) the alphabet size can be

dramatically improved.

__
Revision #1 to TR04-069 | 7th April 2005 00:00
__
#### Improving the alphabet-size in expander based code constructions.

**Abstract:**
In TR04-069 we revisit the construction of high noise, almost

optimal rate list decodable codes of Guruswami \cite{Guru04}, and

note that by replacing the balanced expander component in his

construction with an unbalanced disperser the alphabet size can be

dramatically improved. In this report we point out that the same

type of improvement can be done in various other expander based

constructions given by Guruswami and Indyk in

\cite{guruswami01expanderbased}. We give here one example.

\cite{guruswami01expanderbased} give an explicit

encodable/decodable unique decoding with rate $\epsilon$, relative

distance $(1-\epsilon)$ and alphabet size $2^{O({1 \over \epsilon})}$. we improve the alphabet size to

$2^{2^{polyloglog({1 \over \epsilon})}}$ (assuming one can build an

explicit optimal extractor the alphabet size can get to

$poly({1 \over \epsilon})$).

Unlike the construction in \cite{Guru04}, where the

expanding graph is used only for its expansion properties, the

construction studied here requires both expansion and mixing.

Thus, the improvement is achieved by replacing the balanced

expander used with an unbalanced extractor.

### Paper:

__
TR04-069 | 13th August 2004 00:00
__

#### Improving the alphabet size in high noise, almost optimal rate list decodable codes

**Abstract:**
In this note we revisit the construction of high noise, almost

optimal rate list decodable code of Guruswami ("Better extractors for better codes?")

Guruswami showed that based on optimal extractors one can build a

$(1-\epsilon,O({1 \over \epsilon}))$ list decodable codes of rate

$\Omega({\epsilon \over {log{1 \over \epsilon}}})$ and alphabet

size $2^{O({1 \over \epsilon} \cdot {log{1 \over \epsilon}})}$. We

show that if one replaces the expander component in the

construction with an unbalanced disperser, than one can improve

the alphabet size to $2^{O(log^2{1 \over \epsilon})}$ while

keeping all other parameters the same.