$c^3$-Locally Testable Codes from Lossless Expanders

C. E. Shannon, “A mathematical theory of communication,” The Bell system technical journal, vol. 27, no. 3, pp. 379–423, 1948

1948

Earlier work this paper cites.

R. Gallager, “Low-density parity-check codes,” IRE Transactions on information theory, vol. 8, no. 1, pp. 21–28, 1962

1962

Earlier work this paper cites.

A. Polishchuk and D. A. Spielman, “Nearly-linear size holographic proofs,” in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, 1994, pp. 194–203

1994

Earlier work this paper cites.

S. Arora, F. T. Leighton, and B. M. Maggs, “On-line algorithms for path selection in a nonblocking network,” SIAM Journal on Computing, vol. 25, no. 3, pp. 600–625, 1996

1996

Earlier work this paper cites.

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and the hardness of approximation problems,” Journal of the ACM (JACM), vol. 45, no. 3, pp. 501–555, 1998

1998

Earlier work this paper cites.

E. Ben-Sasson and A. Wigderson, “Short proofs are narrow—resolution made simple,” in Proceedings of the thirty-first annual ACM symposium on Theory of computing, 1999, pp. 517–526

1999

Earlier work this paper cites.

M. Alekhnovich and A. A. Razborov, “Lower bounds for polynomial calculus: Non-binomial case,” in Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 2001, pp. 190–199

2001

Earlier work this paper cites.

M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, “Randomness conductors and constant-degree lossless expanders,” in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002, pp. 659–668

2002

Earlier work this paper cites.

E. Ben-Sasson, M. Sudan, S. Vadhan, and A. Wigderson, “Randomness-efficient low degree tests and short pcps via epsilon-biased sets,” in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003, pp. 612–621

2003

Earlier work this paper cites.

J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi, “Rank bounds and integrality gaps for cutting planes procedures,” in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 2003, pp. 318–327

2003

Cited alongside, same era.

M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, and A. Wigderson, “Pseudorandom generators in propositional proof complexity,” SIAM Journal on Computing, vol. 34, no. 1, pp. 67–88, 2004

2004

Cited alongside, same era.

E. Ben-Sasson and M. Sudan, “Simple pcps with poly-log rate and query complexity,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, 2005, pp. 266–275

2005

Cited alongside, same era.

O. Goldreich and M. Sudan, “Locally testable codes and pcps of almost-linear length,” Journal of the ACM (JACM), vol. 53, no. 4, pp. 558–655, 2006

2006

Cited alongside, same era.

S. Kopparty, O. Meir, N. Ron-Zewi, and S. Saraf, “High-rate locally correctable and locally testable codes with sub-polynomial query complexity,” Journal of the ACM (JACM), vol. 64, no. 2, pp. 1–42, 2017

2017

Later among the works it cites.

O. Goldreich, Introduction to property testing. Cambridge University Press, 2017

2017

Later among the works it cites.

S. Gopi, S. Kopparty, R. Oliveira, N. Ron-Zewi, and S. Saraf, “Locally testable and locally correctable codes approaching the gilbert-varshamov bound,” IEEE Transactions on Information Theory, vol. 64, no. 8, pp. 5813–5831, 2018

2018

Later among the works it cites.

S. Evra, T. Kaufman, and G. Zémor, “Decodable quantum ldpc codes beyond the square root distance barrier using high dimensional expanders,” arXiv preprint arXiv:2004.07935, 2020

Original

2020

Later among the works it cites.

P. Panteleev and G. Kalachev, “Asymptotically good quantum and locally testable classical ldpc codes,” arXiv preprint arXiv:2111.03654, 2021