School of Technology and Computer Science Seminars
Forster's Lower Bound
by Nikhil S. Mande (School of Technology and Computer Science, TIFR)
Friday, May 6, 2016
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
We will talk about the notion of the sign-rank of a {-1, 1}-valued matrix, which measures the robustness 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 sign-rank, and also see implications in lower bounds on communication complexity and circuit complexity in certain models. References: Jurgen Forster. A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity, 2001 Satyanarayana V. Lokam: Complexity Bounds using Linear Algebra |