Workshop on Matrix Rigidity

A matrix is rigid if its rank cannot be reduced significantly by changing a few of its entries. While most matrices are rigid with very strong parameters, the question of explicitly constructing a family of rigid matrices is wide open. In addition to its inherent mathematical appeal, the question of explicit construction of rigid matrices is of great interest due to its connections to various other other lower bound questions in Computational Complexity. Indeed, the notion of rigidity was discovered by Valiant in an attempt to prove lower bounds for linear arithmetic circuits more than four decades ago. Since then, various other applications of this nature have been discovered, e.g. applications in Boolean Circuit Complexity, in Communication Complexity and for Lower bounds for Data Structures.

The goal of the workshop is to have a prolonged discussion on some of the classical as well as more recent results on various aspects Matrix Rigidity. We will start with a couple of tutorials, which will help the unfamiliar audience get acquainted with the notion, followed by a few talks on some of the recent results.


The workshop is a part of FSTTCS 2020 and will be held online on December 13 and 14, 2020. The talks will be live streamed on youtube here. If you have registered for the conference, you would have received a zoom link for the sessions as well.


Josh Alman, Amey Bhangale, Sasha Golovnev, Sivaramakrishnan Natarajan Ramamoorthy, C Ramya, Ben Lee Volk.


Time (IST) Speaker Title
Dec 13, 8:00 am - 9:00 am C Ramya Introduction to matrix rigidity - I, (slides)
Dec 13, 9:10 am - 10:10 am Sasha Golovnev Introduction to matrix rigidity - II, (slides)
Dec 13, 10:20 am - 11:20 am Sivaramakrishnan Natarajan Ramamoorthy On Linear Data Structures and Matrix Rigidity, (slides)
Dec 14, 8:00 am - 9:00 am Josh Alman Rigidity Upper Bounds (slides)
Dec 14, 9:10 am - 10:10 am Ben Lee Volk Polynomial Degree Bounds on Equations for Non-Rigid Matrices, with Applications to Circuit Lower Bounds, (slides)
Dec 14, 10:20 am - 11:20 am Amey Bhangale Constructing rigid matrices from PCPs, (slides)



A list of surveys and recent papers on rigidity can be found here.


Amey Bhangale, Sasha Golovnev, Mrinal Kumar and Amit Sinhababu.

Many thanks to Prerona Chatterjee and C Ramya for their help.