Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On Computing Multilinear Polynomials Using Depth Four Circuits of Bounded Individual Degree
event speaker icon
Suryajith Chillara (University of Haifa)
event date icon
Wednesday, 28.10.2020, 12:30
event location icon
Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code
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 talk about the complexity of computing an entry in the product of d many n×n generic matrices (denoted IMMn,d) by depth four circuits of bounded individual degree.

We show that for all r ≤ na for a fixed constant a, any “syntactic” depth four circuit of bounded individual degree r computing IMMn,d must have size n𝛺(√d) when d ≤ nb (for a fixed constant b ≤ a). This improves upon a previous result of Kayal, Saha and Tavenas [STOC 2016 & Theory of Computing, 2018] who proved a lower bound of (n/r1.1)𝛺(√d/r) for the same.

This talk assumes no relevant background. We will introduce the model of computation, the motivation to study computation of multilinear polynomials by circuits of bounded individual degree and briefly survey relevant results to this restricted model of computation.

More details.

Lecture Video.