Tata Institute of Fundamental Research
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
STCS Colloquium
Speaker:
Nutan Limaye (Indian Institute of Technology
Department of Computer Science and Engineering
Powai
Mumbai 400076)
Organiser:
Piyush Srivastava
Date:
Tuesday, 28 Nov 2017, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $P$. In this talk, we will discuss the algebraic formula complexity of multiplying $d$ many $2x2$ matrices and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear. We will also give two applications of this lower bound to multilinear formula complexity (this is joint work with Suryajith Chillara and Srikanth Srinivasan (IITB)).
| Speaker: | Nutan Limaye (Indian Institute of Technology Department of Computer Science and Engineering Powai Mumbai 400076) |
| Organiser: | Piyush Srivastava |
| Date: | Tuesday, 28 Nov 2017, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $P$. In this talk, we will discuss the algebraic formula complexity of multiplying $d$ many $2x2$ matrices and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear. We will also give two applications of this lower bound to multilinear formula complexity (this is joint work with Suryajith Chillara and Srikanth Srinivasan (IITB)).