Fetching the paper…
Reading the bibliography…
A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x := C(b)$ on at most $q$ coordinates.
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy · 1998
Earlier work this paper cites.
Probabilistic checking of proofs: A new characterization of np
Sanjeev Arora and Shmuel Safra · 1998
Earlier work this paper cites.
On the efficiency of local decoding procedures for error-correcting codes
Jonathan Katz and Luca Trevisan · 2000
Earlier work this paper cites.
On the hardness of information-theoretic multiparty computation
Yuval Ishai and Eyal Kushilevitz · 2004
Earlier work this paper cites.
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Iordanis Kerenidis and Ronald de Wolf · 2004
Earlier work this paper cites.
Some applications of coding theory in computational complexity
Luca Trevisan · 2004
Earlier work this paper cites.
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
Zeev Dvir and Amir Shpilka · 2005
Earlier work this paper cites.
Lower bounds for linear locally decodable codes and private information retrieval
Oded Goldreich, Howard Karloff, Leonard J Schulman, and Luca Trevisan · 2006
Earlier work this paper cites.
Reliable computations based on locally decodable codes
Andrei E. Romashchenko · 2006
Earlier work this paper cites.
New lower bounds for general locally decodable codes
David Woodruff · 2007
Earlier work this paper cites.
Small linear dependencies for binary vectors of low weight
Uriel Feige · 2008
Earlier work this paper cites.
Towards 3-query locally decodable codes of subexponential length
Sergey Yekhanin · 2008
Cited alongside, same era.
3-query locally decodable codes of subexponential length
Klim Efremenko · 2009
Cited alongside, same era.
Error-correcting data structures
Ronald de Wolf · 2009
Cited alongside, same era.
Efficient and error-correcting data structures for membership and polynomial evaluation
Victor Chen, Elena Grigorescu, and Ronald de Wolf · 2010
Cited alongside, same era.
On matrix rigidity and locally self-correctable codes
Zeev Dvir · 2010
Cited alongside, same era.
Locally Decodable Codes and Private Information Retrieval Schemes
Sergey Yekhanin · 2010
Cited alongside, same era.
An introduction to matrix concentration inequalities
Joel A. Tropp · 2015
Later among the works it cites.
On embeddings of ℓ 1 k \ell_{1}^{k} from locally decodable codes
Jop Briët · 2016
Later among the works it cites.
Lower bounds for 2-query lccs over large alphabet
Arnab Bhattacharyya, Sivakanth Gopi, and Avishay Tal · 2017
Later among the works it cites.
Locality in Coding Theory
Sivakanth Gopi · 2018
Later among the works it cites.
Modern coding theory: lecture notes and exercises, 2019
Sivakanth Gopi · 2019
Later among the works it cites.
The kikuchi hierarchy and tensor PCA
Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin · 2011
Cited alongside, same era.
Concentration and moment inequalities for polynomials of independent random variables
Warren Schudy and Maxim Sviridenko · 2012
Cited alongside, same era.
A quadratic lower bound for three-query linear locally decodable codes over any field
David P Woodruff · 2012
Cited alongside, same era.
Locally decodable codes
Sergey Yekhanin · 2012
Cited alongside, same era.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Cited alongside, same era.
Combinatorial lower bounds for 3-query ldcs
Arnab Bhattacharyya, L Sunil Chandran, and Suprovat Ghoshal · 2020
Later among the works it cites.
Strongly refuting all semi-random boolean csps
Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari · 2021
Later among the works it cites.
Algorithms and certificates for boolean CSP refutation: smoothed is no harder than random
Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar · 2022
Later among the works it cites.
A simple and sharper proof of the hypergraph moore bound
Jun-Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty · 2023
Closest in time.