Subspace designs based on algebraic function fields

DOI10.1090/TRAN/7369MaRDI QIDQ4691091zbMATH OpenOpenAlexWikidataFDO

Authors Chaoping Xing, Chen Yuan, Venkatesan Guruswami

Publication date 18 October 2018

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.05992, http://hdl.handle.net/10220/46499

zbMATH Keywords

Reed-Solomon codes

Mathematics Subject Classification ID

Other designs, configurations (05B30) Cyclotomic function fields (class groups, Bernoulli objects, etc.) (11R60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Miscellaneous applications of number theory (11Z05)

Abstract: Subspace designs are a (large) collection of high-dimensional subspaces $H_i$ of $F_q^m$ such that for any low-dimensional subspace $W$, only a small number of subspaces from the collection have non-trivial intersection with $W$; more precisely, the sum of dimensions of $Wcap{H}_i$ is at most some parameter $L$. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically $qgem$). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields, and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over $F^n$ for any field $F$, with logarithmic degree and expansion guarantee for subspaces of dimension $Omega(n/(loglogn))$.

Recommendations

• Subspace designs based on algebraic function fields
• Explicit subspace designs
• scientific article; zbMATH DE number 7250144
• List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
• Dimension Expanders via Rank Condensers

Cites work

• Algebraic Function Fields and Codes
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
• Dimension Expanders via Rank Condensers
• Expansion in SL₂( R) and monotone expanders
• Explicit Class Field Theory for Rational Function Fields
• 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 1716471 (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
• Monotone expanders: constructions and applications
• On automorphism groups of cyclotomic function fields over finite fields
• Optimal rate algebraic list decoding using narrow ray class fields
• The asymptotic behavior of automorphism groups of function fields over finite fields
• Towards dimension expanders over finite fields

Cited in

(14)

• Almost affinely disjoint subspaces
• An asymptotically optimal construction of almost affinely disjoint subspaces
• The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
• Lossless dimension expanders via linearized polynomials and subspace designs
• Explicit subspace designs
• Higgledy-piggledy subspaces and uniform subspace designs
• Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
• Subspace designs based on algebraic function fields
• scientific article; zbMATH DE number 7250144 (Why is no real title available?)
• The asymptotic behavior of automorphism groups of function fields over finite fields
• Almost affinely disjoint subspaces and covering Grassmannian codes
• On subspace designs
• Asymptotically optimal \([2k+1,k,k]_q\)-almost affinely disjoint subspaces
• Variety evasive subspace families

This page was built for publication: Subspace designs based on algebraic function fields

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