Event calendar file
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
|
