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) |
The concept of matrix rigidity was introduced by Valiant (1977) in the context of computing linear transformations by arithmetic circuits and was also studied independently by Grigoriev (1976). A matrix is rigid if it is far in terms of Hamming distance from any low rank matrix.
Matrix rigidity is an interesting and intriguing concept in the sense that it intertwines a combinatorial property such as the sparsity of a matrix with an algebraic property namely the rank of a matrix. Valiant posed the question of constructing an explicit family of rigid matrices. Although we know rigid matrices exist, obtaining explicit constructions of rigid matrices have remained a long-standing open question. This decade has seen tremendous progress towards understanding matrix rigidity. Several explicit constructions of rigid matrices in classes such as E and P^NP were obtained recently. In this talk, we will begin with the story of the birth of matrix rigidity and walk through the recent progress on constructing rigid matrices.
In this talk, we will discuss explicit and semi-explicit constructions of rigid matrices, limitations of the known techniques, and applications of matrix rigidity. We will see that rigid matrices imply lower bounds in circuit and communication complexity, and we will discuss connections between data structures and rigidity. We will also see recent curious relations between coding theory and rigidity. Finally, we will talk about the computational complexity of matrix rigidity.
In this talk, I will discuss (a) linear data structures and some recent connections to matrix (and rectangular) rigidity. Specifically, I will give an overview of the result of Dvir, Golovnev and Weinstein; (b) systematic linear data structures and show that they are equivalent to rectangular rigidity; and (c) a rigidity lower bound for the set of vectors that correspond to rank one matrices; (b) and (c) are joint work with Cyrus Rashtchian.
The grand challenge for matrix rigidity is to show that some family of explicit matrices is rigid. A recent line of work has shown that many of the previous leading candidate matrices, including Hadamard, Fourier, and Toeplitz matrices, are actually not rigid enough to prove lower bounds using Valiant's approach. In this talk, I'll give an overview of these rigidity upper bounds, and the techniques used to prove them. I'll present joint work with Ryan Williams showing that the Walsh-Hadamard transform is not rigid, and then give an overview of further upper bounds by Zeev Dvir, Benjamin Edelman, and Allen Liu.
Basic algebraic geometry implies the existence of nonzero polynomials which vanish on all non-rigid matrices. Such a polynomial P may serve as a "proof" that a matrix M is rigid, by showing that P(M) is nonzero. However, showing the nonzeroness of P(M) is often only feasible if P is "simple".
One notion of simplicity is being low degree: we first prove that there exists such a polynomial whose degree is at most poly(n). This improves upon previous exponential upper bounds.
Another notion of simplicity is being efficiently computable. Using this point of view, we prove that any derandomization of the polynomial identity testing problem would imply new circuit lower bounds in algebraic complexity theory: either a PSPACE construction of a polynomial family which requires super-polynomial size arithmetic circuits, or an efficient construction using an NP oracle of rigid matrices with near-optimal parameters . This is similar (but incomparable) to a result of Kabanets and Impagliazzo.
(Based on a joint work with Mrinal Kumar)
Constructing rigid matrices has been a long-standing open problem in computational complexity theory since their introduction by Valiant more than four decades ago. The study of Probabilistically Checkable Proofs (PCPs) started in the late 80s. PCPs provide a format of rewriting classical NP-proofs that can be efficiently verified based only on a small number of random queries into the rewritten proof.
In this talk, I will go over the novel approach of the construction of rigid matrices using PCPs by Alman and Chen. I will also talk about 'rectangular PCPs' (PCPs with some additional structure) and show how to construct rigid(er) matrices using rectangular PCPs.
These constructions give non-trivial lower bounds in the area of communication complexity. Although they still do not attain the rank bounds required for Valiant’s lower bounds, they vastly improve the state of the art of explicit rigid matrix constructions.
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.