Exponential lower bound for 2-query locally decodable codes via a quantum argument

DOI10.1016/j.jcss.2004.04.007zbMath1084.68044OpenAlexW4230909286MaRDI QIDQ5917576

Ronald de Wolf, Iordanis Kerenidis

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.007

zbMATH Keywords

Quantum computingLocally decodable codesPrivate information retrieval

Mathematics Subject Classification ID

Quantum computation (81P68) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information storage and retrieval of data (68P20)

Related Items (20)

Certifying equality with limited interaction ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Query-efficient locally decodable codes of subexponential length ⋮ On matrix rigidity and locally self-correctable codes ⋮ Evolutionary algorithms for quantum computers ⋮ Foundations of Homomorphic Secret Sharing ⋮ On coset leader graphs of structured linear codes ⋮ Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Quantum private information retrieval has linear communication complexity ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ High-entropy dual functions over finite fields and locally decodable codes ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Outlaw distributions and locally decodable codes ⋮ High-rate codes with sublinear-time decoding ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for linear locally decodable codes and private information retrieval
• Highly resilient correctors for polynomials
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Linking classical and quantum key agreement: Is there a classical analog to bound entanglement?
• Pseudorandom generators without the XOR Lemma (extended abstract)
• Expander codes
• Random-Self-Reducibility of Complete Sets
• Private information retrieval
• On the efficiency of local decoding procedures for error-correcting codes
• Are bitvectors optimal?
• Extractors
• Upper bound on the communication complexity of private information retrieval
• Interaction in quantum communication and the complexity of set disjointness
• Quantum lower bounds by polynomials
• Lower bounds for adaptive locally decodable codes
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

This page was built for publication: Exponential lower bound for 2-query locally decodable codes via a quantum argument