Name
Abstract | ||
|---|---|---|
A subspace design is a collection H_1, H_2, ·, H_M of subspaces of F_qm with the property that no low-dimensional subspace W of F_qm intersects too many subspaces of the collection. Subspace designs were introduced by Guru swami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters. Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial P_W that has several roots for each H_i that non-trivially intersects W. The construction of P_W is based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/FOCS.2013.71 | Foundations of Computer Science |
Keywords | Field | DocType |
determinants,polynomials,probability,classical wronskian determinant,deterministic polynomial time construction,explicit subspace designs,folded wronskian determinant,list-decodable codes,low-dimensional subspace,multiplicity roots,nonzero low-degree polynomial,probabilistic construction,structured roots,subspace design property,univariate polynomials,algebraic coding,list-decoding,polynomial method,pseudorandomness,reed-solomon codes | Discrete mathematics,Combinatorics,Linear independence,Finite field,Polynomial,Subspace topology,Wronskian,Linear subspace,Time complexity,Univariate,Mathematics | Conference |
Volume | Issue | ISSN |
36 | 2 | 0272-5428 |
Citations | PageRank | References |
12 | 0.63 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Guruswami | 1 | 3205 | 247.96 |
| Swastik Kopparty | 2 | 384 | 32.89 |