Title: Explicit Subspace Designs
Speaker: Swastik Kopparty, Rutgers
Date: Tuesday, April 23, 2013 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
A subspace design is a collection {H1, H2, .., HM} of subspaces of F_q^m with the property that no low-dimensional subspace W of F_q^m intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing, who used them to give randomized constructions of optimal rate list-decodable codes over constant size alphabets. Subspace designs were the only non-explicit part of their construction. In this talk, I will describe some simple explicit constructions of subspace designs. The constructions themselves are natural and easily described, and are based on univariate polynomials over finite fields. 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 Hi that non-trivially intersects W. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with highly structured roots or many high multiplicity roots tend to be linearly independent. Joint work with Venkatesan Guruswami
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math