Tata Institute of Fundamental Research
Forster's Lower Bound
STCS Student Seminar
Speaker:
Nikhil S Mande
Organiser:
Nikhil S Mande
Date:
Friday, 6 May 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Nikhil S Mande |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 6 May 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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
References:
Jurgen Forster. A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity, 2001
Satyanarayana V. Lokam: Complexity Bounds using Linear Algebra