Explicit subspace designs (Q2400105)

An \((s,A)\) subspace design is a set of linear subspaces \(H_1, \dots, H_M\) of \(F_q^m\) such that for every \(s\)-dimensional subspace \(W\) of \(F_q^m\) at most \(A\) of the \(H_i\) intersect \(W\) non-trivially. In this paper, the authors refine the construction of the first author and \textit{C. Xing} [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 843--852 (2013; Zbl 1293.94110)], who gave a randomized construction of optimal rate list-decodable codes over constant sized large alphabets and sublogarithmic list size, to give an explicit construction based on univariate polynomials over a finite field in deterministic polynomial time.