BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/681
DTSTAMP:20230914T125934Z
SUMMARY:Forster's Lower Bound
DESCRIPTION:Speaker: Nikhil S Mande\n\nAbstract: \nWe will talk about the n
otion of the sign-rank of a {-1\, 1}-valued matrix\, which measures the ro
bustness of it's rank under sign preserving changes. We will first see a
neat geometric interpretation of the sign-rank\, and then see how showing
an upper bound on the spectral norm of A implies a lower bound on its sig
n-rank\, and also see implications in lower bounds on communication comple
xity and circuit complexity in certain models.\n\nReferences:\nJurgen Fors
ter. A Linear Lower Bound on the Unbounded Error Probabilistic Communicati
on Complexity\, 2001\nSatyanarayana V. Lokam: Complexity Bounds using Line
ar Algebra\n
URL:https://www.tcs.tifr.res.in/web/events/681
DTSTART;TZID=Asia/Kolkata:20160506T160000
DTEND;TZID=Asia/Kolkata:20160506T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR