Lossless dimension expanders via linearized polynomials and subspace designs
A collection of \(d\) linear maps \(\Gamma_1,\ldots,\Gamma_d\) on an \(n\)-dimensional vector space \(F^n\) over a (finite) field \(F\), is called an \((\eta,\beta)\)-dimension expander of degree \(d\), if for every subspace \(U\) of dimension at most \(\eta n\), the dimension of \(\sum_{j=1}^d\Gamma_j(U)\) is at least \(\beta\dim(U)\). Though a random collection of \(d=O(1)\) linear maps on a vector space over a finite field offers excellent (lossless) expansion properties \(\beta \approx d\) for \(\eta\ge \Omega(1/d)\), it is not trivial to give explicit constructions even for modest expansion factor \(\beta = 1+\varepsilon\). For large finite fields \(|F|\ge \Omega(n)\), the author's constructions achieve lossless expansion \(\beta\ge (1-\varepsilon)d\) and \(\eta\ge (1-\varepsilon)/d\). Moreover they also obtain degree-proportional expansion for smaller field sizes. As the authors indicate, prior to this work, no explicit constructions of degree-proportional dimension expanders were known.
- A note on subspace evasive sets
- Algebraic Function Fields and Codes
- Algebraic geometry in coding theory and cryptography
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Dimension expanders
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Evading subspaces over large fields and explicit list-decodable rank-metric codes
- Expanders and dimensional expansion
- Expansion in SL₂( R) and monotone expanders
- Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
- Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs
- Explicit subspace designs
- Folded codes from function field towers and improved optimal rate list decoding
- scientific article; zbMATH DE number 607286 (Why is no real title available?)
- scientific article; zbMATH DE number 2196516 (Why is no real title available?)
- Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
- List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Monotone expanders: constructions and applications
- On identity testing of tensors, low-rank recovery and compressed sensing
- Pseudorandomness
- Quantum expanders from any classical Cayley graph expander
- Subspace designs based on algebraic function fields
- Subspace evasive sets
- Theory of codes with maximum rank distance
- Towards dimension expanders over finite fields
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- Subspace designs based on algebraic function fields
- scientific article; zbMATH DE number 7250144 (Why is no real title available?)
- Dimension expanders via quiver representations
- Towards dimension expanders over finite fields
- On MSRD codes, h-designs and disjoint maximum scattered linear sets
- Gabidulin codes achieve list decoding capacity with an order-optimal column-to-row ratio
This page was built for publication: Lossless dimension expanders via linearized polynomials and subspace designs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2236661)
