ECCC-Report TR04-069https://eccc.weizmann.ac.il/report/2004/069Comments and Revisions published for TR04-069en-usSun, 05 Feb 2006 00:00:00 +0200
Revision 2
| Improving the Alphabet Size in Expander Based Code Constructions |
Eran Rom
https://eccc.weizmann.ac.il/report/2004/069#revision2Various 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.
Sun, 05 Feb 2006 00:00:00 +0200https://eccc.weizmann.ac.il/report/2004/069#revision2
Revision 1
| Improving the alphabet-size in expander based code constructions. |
Amnon Ta-Shma,
Eran Rom
https://eccc.weizmann.ac.il/report/2004/069#revision1In 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.
Thu, 07 Apr 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2004/069#revision1
Paper TR04-069
| Improving the alphabet size in high noise, almost optimal rate list decodable codes |
Eran Rom,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2004/069In 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.
Mon, 16 Aug 2004 17:05:41 +0300https://eccc.weizmann.ac.il/report/2004/069