Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-007 | 9th January 2009 00:00

Tensor Products of Weakly Smooth Codes are Robust

RSS-Feed




TR09-007
Authors: Eli Ben-Sasson, Michael Viderman
Publication: 26th January 2009 19:53
Downloads: 3245
Keywords: 


Abstract:

We continue the study of {\em robust} tensor codes and expand the
class of base codes that can be used as a starting point for the
construction of locally testable codes via robust two-wise tensor
products. In particular, we show that all unique-neighbor expander
codes and all locally correctable codes, when tensored with any
other good-distance code, are robust and hence can be used to
construct locally testable codes. Previous works by required stronger expansion properties to obtain locally testable codes.

Our proofs follow by defining the notion of {\em weakly smooth}
codes that generalize the {\em smooth} codes of I.Dinur et al. We
show that weakly smooth codes are sufficient for constructing robust
tensor codes. Using the weaker definition, we are able to expand the
family of base codes to include the aforementioned ones.



ISSN 1433-8092 | Imprint