Tata Institute of Fundamental Research
Subspace Designs
STCS Seminar
Speaker:
Venkatesan Guruswami (Carnegie Mellon University
Department of Computer Science
5000 Forbes Avenue
Pittsburgh, PA 15213
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Wednesday, 25 Jan 2017, 17:00 to 19:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A subspace design is a (large) collection of subspaces of F_q^n, each of small co-dimension, such that for any low-dimensional subspace W, only a small number from the collection have a non-trivial intersection with W. This notion was put forth in the context of algebraic list decoding where it enabled the construction of optimal redundancy list-decodable codes over small alphabets and for the rank-metric. An explicit construction of subspace designs over large fields with near-optimal parameters was later given based on polynomials; curiously, this construction is closely related to folded Reed-Solomon codes, the list-decodable codes which motivated subspace designs in the first place.
Subspace designs have since been found to play a central role in the emerging theory of "linear-algebraic pseudorandomness” which aims to understand analogs of Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In particular, they yield “rank condensers” which in turn enable construction of dimension expanders, the linear-algebraic analog of (vertex) expanders. Via this connection, the known explicit construction of subspace designs yield simple constant-degree dimension expanders over F_q^n when q \ge poly(n). Subspace designs over any field were recently constructed based on algebraic function fields; while this incurs a slight worsening of parameters, it raises hope that perhaps one can get constant-degree dimension expanders over any field via this route (the only known explicit construction for arbitrary fields, via monotone expanders, is quite complicated).
This talk will survey these developments revolving around subspace designs, their construction, and connections (based on several joint works with Chaoping Xing, Swastik Kopparty, Michael Forbes, and Chen Yuan).
| Speaker: | Venkatesan Guruswami (Carnegie Mellon University Department of Computer Science 5000 Forbes Avenue Pittsburgh, PA 15213 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Wednesday, 25 Jan 2017, 17:00 to 19:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
A subspace design is a (large) collection of subspaces of F_q^n, each of small co-dimension, such that for any low-dimensional subspace W, only a small number from the collection have a non-trivial intersection with W. This notion was put forth in the context of algebraic list decoding where it enabled the construction of optimal redundancy list-decodable codes over small alphabets and for the rank-metric. An explicit construction of subspace designs over large fields with near-optimal parameters was later given based on polynomials; curiously, this construction is closely related to folded Reed-Solomon codes, the list-decodable codes which motivated subspace designs in the first place.
Subspace designs have since been found to play a central role in the emerging theory of "linear-algebraic pseudorandomness” which aims to understand analogs of Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In particular, they yield “rank condensers” which in turn enable construction of dimension expanders, the linear-algebraic analog of (vertex) expanders. Via this connection, the known explicit construction of subspace designs yield simple constant-degree dimension expanders over F_q^n when q \ge poly(n). Subspace designs over any field were recently constructed based on algebraic function fields; while this incurs a slight worsening of parameters, it raises hope that perhaps one can get constant-degree dimension expanders over any field via this route (the only known explicit construction for arbitrary fields, via monotone expanders, is quite complicated).
This talk will survey these developments revolving around subspace designs, their construction, and connections (based on several joint works with Chaoping Xing, Swastik Kopparty, Michael Forbes, and Chen Yuan).
Subspace designs have since been found to play a central role in the emerging theory of "linear-algebraic pseudorandomness” which aims to understand analogs of Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In particular, they yield “rank condensers” which in turn enable construction of dimension expanders, the linear-algebraic analog of (vertex) expanders. Via this connection, the known explicit construction of subspace designs yield simple constant-degree dimension expanders over F_q^n when q \ge poly(n). Subspace designs over any field were recently constructed based on algebraic function fields; while this incurs a slight worsening of parameters, it raises hope that perhaps one can get constant-degree dimension expanders over any field via this route (the only known explicit construction for arbitrary fields, via monotone expanders, is quite complicated).
This talk will survey these developments revolving around subspace designs, their construction, and connections (based on several joint works with Chaoping Xing, Swastik Kopparty, Michael Forbes, and Chen Yuan).