Towards 3-query locally decodable codes of subexponential length
By Sergey Yekhanin. JACM, 2008
492 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/703f1041709babdcda4852a2e81e63cbd686de7d
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Salim el Rouayheb
- Ian Goldberg
- Elette Boyle
- Razane Tajeddine
- Niv Gilboa
- Yuval Ishai
- Casey Devet
- Oliver Wilhelm Gnilke
In Computer Networks and Communications
- Salim el Rouayheb
- Razane Tajeddine
- Elette Boyle
- Niv Gilboa
- Yuval Ishai
- Siddhartha Kumar
- Eirik Rosnes
- Alexandre Graell i Amat
Citations in the corpus
- Function Secret Sharing (2015, background): “Even with the above relaxations, the asymptotic communication complexity of the best known information-theoretic PIR protocols [15, 47, 21, 4, 6, 19] is worse than that of DPF-based protocols.”
- Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, background): “[2], [3] followed by a significant amount of research in this area [4]–[8], [11], [12].”
- On the Locality of Codeword Symbols (2011, background): “Locally decodable codes.”
- Private information retrieval in distributed storage systems using an arbitrary linear code (2016, background): “The communication cost in [1], [2] was further reduced in [3]–[5].”
- Optimally Robust Private Information Retrieval (2012, background): “While much of the theoretical work on PIR focuses strictly on minimizing the amount of data transferred [15] [38], in a practical setting we must take other aspects, particularly the computational performance, into account.”
- Distributed Point Functions and Their Applications (2014, background): “The best known 3-server protocols [33, 14, 4] have queries of size 2 √ logn·log logn) and single-bit answers.”
- Revisiting the Computational Practicality of Private Information Retrieval (2011, background): “Most of the subsequent work has tried to improve the communication complexity bounds [4, 10, 21, 51], while some others [5, 6, 11, 23, 26] have additionally addressed such problems as amortizing server-side computational overheads, and improving query robustness, amongst others.”