An optimal lower bound for 2-query locally decodable linear codes

DOI10.1016/J.IPL.2005.11.009zbMath1184.68245OpenAlexW2078058008MaRDI QIDQ1045948

Satyanarayana V. Lokam, Dungjade Shiowattana

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.11.009

zbMATH Keywords

computational complexitycryptographycombinatorial problems

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Decoding (94B35)

Related Items (1)

Query-efficient locally decodable codes of subexponential length

Cites Work

• Unnamed Item
• Unnamed Item
• Expander codes
• On the efficiency of local decoding procedures for error-correcting codes
• Extractors
• Upper bound on the communication complexity of private information retrieval
• Lower bounds for adaptive locally decodable codes
• Automata, Languages and Programming

This page was built for publication: An optimal lower bound for 2-query locally decodable linear codes