We consider the problem of constructing explicit matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question, this problem appears in various incarnations in computer science. In the talk we will survey the background and motivation, prove some lower bounds, and present the main open problems.
Based on a joint work with Mrinal Kumar.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
