BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/748
DTSTAMP:20230914T125936Z
SUMMARY:Subspace Designs
DESCRIPTION:Speaker: Venkatesan Guruswami (Carnegie Mellon University\nDepa
rtment of Computer Science\n5000 Forbes Avenue\nPittsburgh\, PA 15213\nUni
ted States of America)\n\nAbstract: \nA subspace design is a (large) colle
ction of subspaces of F_q^n\, each of small co-dimension\, such that for a
ny low-dimensional subspace W\, only a small number from the collection ha
ve a non-trivial intersection with W. This notion was put forth in the con
text of algebraic list decoding where it enabled the construction of optim
al redundancy list-decodable codes over small alphabets and for the rank-m
etric. 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.\
n\nSubspace designs have since been found to play a central role in the em
erging theory of "linear-algebraic pseudorandomness” which aims to under
stand 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\, t
he linear-algebraic analog of (vertex) expanders. Via this connection\, th
e known explicit construction of subspace designs yield simple constant-de
gree dimension expanders over F_q^n when q \\ge poly(n). Subspace designs
over any field were recently constructed based on algebraic function field
s\; while this incurs a slight worsening of parameters\, it raises hope th
at 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).\n\nThis talk will survey
these developments revolving around subspace designs\, their construction
\, and connections (based on several joint works with Chaoping Xing\, Swas
tik Kopparty\, Michael Forbes\, and Chen Yuan).\n
URL:https://www.tcs.tifr.res.in/web/events/748
DTSTART;TZID=Asia/Kolkata:20170125T170000
DTEND;TZID=Asia/Kolkata:20170125T190000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR