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.

Parent

References

[1]
E. Ben-Sasson et al., “Randomness-efficient low degree tests and short PCPs via epsilon-biased sets”, Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC ’03 (2003) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: bssvw-ltc

Cite as:
“Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/bssvw-ltc
BibTeX:
@incollection{eczoo_bssvw-ltc, title={Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, 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.), 2022. https://errorcorrectionzoo.org/c/bssvw-ltc

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