Fetching the paper…
Reading the bibliography…
We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$.
On the efficiency of local decoding procedures for error-correcting codes
Jonathan Katz and Luca Trevisan · 2000
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.
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.
Rainbow Turán problems
Peter Keevash, Dhruv Mubayi, Benny Sudakov, and Jacques Verstraëte · 2007
Earlier work this paper cites.
A note on Yekhanin’s locally decodable codes
Prasad Raghavendra · 2007
Earlier work this paper cites.
New lower bounds for general locally decodable codes
David Woodruff · 2007
Earlier work this paper cites.
Towards 3-query locally decodable codes of subexponential length
Sergey Yekhanin · 2008
Earlier work this paper cites.
Matching vector codes
Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin · 2011
Earlier work this paper cites.
3-query locally decodable codes of subexponential length
Klim Efremenko · 2012
Earlier work this paper cites.
A quadratic lower bound for three-query linear locally decodable codes over any field
David P. Woodruff · 2012
Earlier work this paper cites.
Locally decodable codes
Sergey Yekhanin · 2012
Earlier work this paper cites.
Rainbow Turán problem for even cycles
Shagnik Das, Choongbum Lee, and Benny Sudakov · 2013
Earlier work this paper cites.
New affine-invariant codes from lifting
Alan Guo, Swastik Kopparty, and Madhu Sudan · 2013
Earlier work this paper cites.
Improved rank bounds for design matrices and a new proof of kelly’s theorem
Zeev Dvir, Shubhangi Saraf, and Avi Wigderson · 2014
Earlier work this paper cites.
High-rate codes with sublinear-time decoding
Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin · 2014
Earlier work this paper cites.
Local correctability of expander codes
Brett Hemenway, Rafail Ostrovsky, and Mary Wootters · 2015
Cited alongside, same era.
Locally decodable codes for edit distance
Rafail Ostrovsky and Anat Paskin-Cherniavsky · 2015
Cited alongside, same era.
High-rate locally correctable and locally testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf · 2017
Cited alongside, same era.
Locally testable and locally correctable codes approaching the gilbert-varshamov bound
Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf · 2018
Cited alongside, same era.
Locality in coding theory
Sivakanth Gopi · 2018
Cited alongside, same era.
A lower bound for relaxed locally decodable codes
Tom Gur and Oded Lachish · 2019
Rainbow cycles in properly edge-colored graphs
Jaehoon Kim, Joonkyung Lee, Hong Liu, and Tuan Tran · 2022
Later among the works it cites.
Robust (rainbow) subdivisions and simplicial cycles
István Tomon · 2022
Later among the works it cites.
Essentially tight bounds for rainbow cycles in proper edge-colourings
Noga Alon, Matija Bucić, Lisa Sauermann, Dmitrii Zakharov, and Or Zamir · 2023
Later among the works it cites.
A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K Kothari, and Peter Manohar · 2023
Later among the works it cites.
On relaxed locally decodable codes for hamming and insertion-deletion errors
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Locally decodable/correctable codes for insertions and deletions
Alexander R Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu · 2020
Cited alongside, same era.
Relaxed locally correctable codes
Tom Gur, Govind Ramnarayan, and Ron Rothblum · 2020
Cited alongside, same era.
On coset leader graphs of structured linear codes
Eran Iceland and Alex Samorodnitsky · 2020
Cited alongside, same era.
Relaxed locally correctable codes with improved parameters
Vahid R Asadi and Igor Shinkar · 2021
Cited alongside, same era.
Relaxed locally correctable codes in computationally bounded channels
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, and Samson Zhou · 2021
Cited alongside, same era.
Exponential lower bounds for locally decodable and correctable codes for insertions and deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu · 2022
Cited alongside, same era.
Alexander R Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu · 2023
Later among the works it cites.
Asymptotically-good RLCCs with ( log n ) 2 + o ( 1 ) (\log{n})^{2+o(1)} queries
Gil Cohen and Tal Yankovitz · 2023
Later among the works it cites.
Constant query local decoding against deletions is impossible
Meghal Gupta · 2023
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
Later among the works it cites.
Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
Oliver Janzer · 2023
Later among the works it cites.
An exponential lower bound for linear 3-query locally correctable codes
Pravesh K Kothari and Peter Manohar · 2023
Later among the works it cites.
Relaxed local correctability from local testing
Vinayak M Kumar and Geoffrey Mon · 2023
Later among the works it cites.
Personal communication, 2024
Jun-Ting Hsieh, Pravesh Kothari, and Peter Manohar · 2024
Closest in time.
Small even covers, locally decodable codes and restricted subgraphs of edge-colored Kikuchi graphs
Jun-Ting Hsieh, Pravesh K Kothari, Sidhanth Mohanty, David Munhá Correia, and Benny Sudakov · 2024
Closest in time.
Superpolynomial lower bounds for smooth 3-LCCs and sharp bounds for designs
Pravesh Kothari and Peter Manohar · 2024
Closest in time.
A stronger bound for linear 3-LCC
Tal Yankovitz · 2024
Closest in time.