[Jump to code hierarchy]

Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code[1]

Description

Locally testable \([n,k,d]\) code with \(n = k \cdot 2^{\tilde{O}(\sqrt{\log k})}\) and asymptotically constant query complexity, where \(\tilde{O}(f)=O(f\cdot (\log f)^c)\) for some fixed constant \(c\).

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Binary linear LTCLinear \(q\)-ary LTC ECC
Parents
Binary linear LTC
Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code

References

[1]
E. Ben-Sasson, M. Sudan, S. Vadhan, and A. Wigderson, “Randomness-efficient low degree tests and short PCPs via epsilon-biased sets”, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing 612 (2003) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: bssvw-ltc

Cite as:
“Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/bssvw-ltc, arXiv:2606.11484
BibTeX:
@incollection{eczoo_bssvw-ltc,
title={Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/bssvw-ltc}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/bssvw-ltc

Cite as:

“Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/bssvw-ltc, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/ltc/bssvw-ltc.yml.