On matrix rigidity and locally self-correctable codes
From MaRDI portal
Publication:645122
DOI10.1007/s00037-011-0009-1zbMath1250.94064OpenAlexW2126216220MaRDI QIDQ645122
Publication date: 8 November 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0009-1
Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)
Related Items (5)
Complexity of linear circuits and geometry ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ Sylvester-Gallai for arrangements of subspaces ⋮ High-rate codes with sublinear-time decoding ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- More on average case vs approximation complexity
- Lower bounds for linear locally decodable codes and private information retrieval
- A survey of Sylvester's problem and its generalizations
- Matching Vector Codes
- On the efficiency of local decoding procedures for error-correcting codes
- Complexity Lower Bounds using Linear Algebra
- Towards 3-query locally decodable codes of subexponential length
- Locally Testable Cyclic Codes
- On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
- Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Designing programs that check their work
- 3-query locally decodable codes of subexponential length
- Some Applications of Coding Theory in Computational Complexity
- Theory and Applications of Models of Computation
- Natural proofs
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
This page was built for publication: On matrix rigidity and locally self-correctable codes
