scientific article; zbMATH DE number 2019623

MaRDI QIDQ4440426zbMATH OpenFDO

Authors Kenji Obata

Publication date 17 December 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2483/24830039.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05) Decoding (94B35)

Recommendations

• Lower bounds for linear locally decodable codes and private information retrieval
• Automata, Languages and Programming
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• A quadratic lower bound for three-query linear locally decodable codes over any field

Cited in

(15)

• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Lower bounds for linear locally decodable codes and private information retrieval
• Lower bounds for 2-query LCCs over large alphabet
• Lower bounds for adaptive locally decodable codes
• An optimal lower bound for 2-query locally decodable linear codes
• Bounds on \(2\)-query codeword testing
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Query-efficient locally decodable codes of subexponential length
• On the power of relaxed local decoding algorithms
• A quadratic lower bound for three-query linear locally decodable codes over any field
• A quadratic lower bound for three-query linear locally decodable codes over any field
• High-rate codes with sublinear-time decoding
• Towards lower bounds on locally testable codes via density arguments
• General constructions for information-theoretic private information retrieval

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4440426)