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)

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).