Matrix Rigidity and the Croot-Lev-Pach Lemma

Zeev Dvir, Benjamin L. EdelmanTheory Comput 2019 · OpenReview

TL;DR

This paper explores the concept of "matrix rigidity," a property crucial for proving lower bounds in circuit complexity. The authors demonstrate a new class of matrices, constructed from simple functions over finite fields, that are surprisingly not rigid, meaning they can be made low-rank with only a few changes. This finding offers a fresh perspective on why finding rigid matrices has been so challenging and may guide future research towards stronger complexity lower bounds.

What Problem Does This Paper Address?

Proving unconditional lower bounds for computational complexity is a long-standing challenge. One promising avenue is to find "rigid matrices"—matrices that are far from any low-rank matrix. If we could find an explicit rigid matrix, it would directly lead to proving that certain computational tasks cannot be performed efficiently by linear circuits. Despite decades of effort, no such explicit rigid matrix has been found. Recent work has even shown that some previously suspected candidates, like the Hadamard matrix, are not rigid enough. This paper tackles the question of why finding rigid matrices is so difficult by investigating a new family of matrices and uncovering a phenomenon of "non-rigidity" that sheds light on this challenge.

Methods

The core of the paper's contribution lies in its application of a recent lemma by Croot, Lev, and Pach (CLP lemma). This lemma provides a bound on the rank of matrices whose entries are given by a polynomial evaluated at the sum of row and column indices (i.e., $M_{x,y} = P(x+y)$). The authors extend this by considering matrices where the entries are given by any function $f(x+y)$ over a finite field. They leverage the fact that any such function can be well-approximated by a polynomial. By carefully choosing the degree of this approximating polynomial and using bounds on the number of monomials of a certain degree (via Claim 2.2 and Corollary 2.4), they show that the matrix $M_{x,y} = f(x+y)$ can be made low-rank by changing only a small number of its entries.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Why" Behind Non-Rigidity: The paper provides a concrete reason why certain structured matrices, specifically those of the form $f(x+y)$ over finite fields, are not rigid. This is a significant step in understanding the landscape of matrix rigidity.
  • Leveraging the CLP Lemma: The work elegantly demonstrates the power of the Croot-Lev-Pach lemma beyond its original application to cap sets, showing its utility in proving matrix properties relevant to complexity theory.
  • Function Approximation is Key: The insight that any function can be approximated by a polynomial, and that this approximation can be controlled in terms of the number of differing entries, is central to the proof. This allows the authors to bridge the gap between arbitrary functions and the polynomial-based CLP lemma.
  • Finite Fields Matter: The results highlight the specific properties of finite fields that contribute to this non-rigidity, posing an open question about whether similar phenomena hold over infinite fields like the rationals or complex numbers.

Key Results

The main result is Theorem 1.3, which states that for any finite field $\mathbb{F}_q$ and any function $f: \mathbb{F}_q^n \to \mathbb{F}_q$, the $q^n \times q^n$ matrix $M$ defined by $M_{x,y} = f(x+y)$ is not "Valiant-rigid." Specifically, for any $\epsilon > 0$, there exists $\epsilon' > 0$ such that the rank-$r$ rigidity of $M$ (where $r = N^{1-\epsilon'}$) is at most $N^{1+\epsilon}$, where $N=q^n$. This means that only a small fraction of entries need to be changed to reduce the matrix's rank significantly.

Limitations and Future Work

The authors acknowledge that their result holds for matrices over finite fields. A key open question is whether Theorem 1.3 still holds if the function $f$ is defined over the rational or complex numbers. This would have implications for understanding the rigidity of matrices like the Hadamard matrix over these fields. Future work could also explore other group structures for the row/column indices beyond $\mathbb{F}_q^n$, potentially leading to higher rigidity. The paper's findings are intended to guide future research towards proving stronger rigidity results, which are essential for establishing unconditional circuit lower bounds.

Summary updated

BibTeX
@inproceedings{dvir2019matrix,
  author = {Zeev Dvir and Benjamin L. Edelman},
  title = {{Matrix Rigidity and the Croot-Lev-Pach Lemma}},
  booktitle = {Theory Comput},
  year = {2019},
  url = {https://openreview.net/forum?id=qDi19nVj1hT},
}
Figure