Subspace evasive sets
From MaRDI portal
Abstract: In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) who showed how such constructions over the binary field can be used to construct explicit Ramsey graphs. More recently, Guruswami (2011) showed that, over large finite fields (of size polynomial in n), subspace evasive sets can be used to obtain explicit list-decodable codes with optimal rate and constant list-size. In this work we construct subspace evasive sets over large fields and use them to reduce the list size of folded Reed-Solomon codes form poly(n) to a constant.
Recommendations
Cited in
(27)- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Lossless dimension expanders via linearized polynomials and subspace designs
- Explicit subspace designs
- New MRD codes from linear cutting blocking sets
- Evasiveness of subgraph containment and related properties
- List-decoding multiplicity codes
- Extractors for polynomial sources over fields of constant order and small characteristic
- Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
- Variety evasive sets
- Group homomorphisms as error correcting codes
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- Improved list-decodability of random linear binary codes
- Low-density parity-check codes achieve list-decoding capacity
- Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
- Local list recovery of high-rate tensor codes and applications
- scientific article; zbMATH DE number 7250144 (Why is no real title available?)
- A note on subspace evasive sets
- Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
- Evasive subspaces
- Variety evasive subspace families
- Short rank-metric codes and scattered subspaces
- Evasive sets, covering by subspaces, and point-hyperplane incidences
- Exceptional scattered sequences
- Avoiding intersections of given size in finite affine spaces \(\operatorname{AG}(n,2)\)
- Random Turán and counting results for general position sets over finite fields
- Maximum in-general-position set in a random subset of \(\mathbb{F}_q^d\)
- Near-optimal list-recovery of linear code families
This page was built for publication: Subspace evasive sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415486)
