Skip to main content

Matrix Rigidity and the Croot-Lev-Pach Lemma

Author(s): Dvir, Zeev; Edelman, Benjamin L

To refer to this page use:
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 qn×qn matrix M of the form M(x,y)=f(x+y), where f:𝔽nq→𝔽q is any function and 𝔽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).
Publication Date: 2019
Citation: Dvir, Zeev, and Benjamin L. Edelman. "Matrix Rigidity and the Croot-Lev-Pach Lemma." Theory of Computing 15, no. 8 (2019): pp. 1-7. doi: 10.4086/toc.2019.v015a008
DOI: 10.4086/toc.2019.v015a008
ISSN: 1557-2862
Pages: 1 - 7
Type of Material: Journal Article
Journal/Proceeding Title: Theory of Computing
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.