Theory of Computing
-------------------
Title     : Matrix Rigidity and the Croot-Lev-Pach Lemma
Authors   : Zeev Dvir and Benjamin L. Edelman
Volume    : 15
Number    : 8
Pages     : 1-7
URL       : https://theoryofcomputing.org/articles/v015a008

Abstract
--------

Matrix rigidity is a notion put forth by Valiant (1977) as a means for
proving arithmetic circuit lower bounds. A matrix is rigid if it is
far, in Hamming distance, from any low-rank matrix. Despite decades of
effort, no explicit matrix rigid enough to carry out Valiant's plan
has been found. Recently, Alman and Williams (STOC'17) showed that,
contrary to common belief, the Walsh--Hadamard matrices cannot be
used for Valiant's program as they are not sufficiently rigid.

Our main result is a similar non-rigidity theorem for _any_ 
$q^n \times q^n$ matrix $M$ of the form $M(x,y) = f(x+y)$, where
$f:\mathbb{F}_q^n \to \mathbb{F}_q$ is any function and $\mathbb{F}_q$
is a fixed finite field of $q$ elements ($n$ goes to infinity). The
theorem follows almost immediately from a recent lemma of Croot, Lev
and Pach (2017) which is also the main ingredient in the recent
solution of the famous cap-set problem by Ellenberg and Gijswijt (2017).