Matrix rigidity and the Croot-Lev-Pach lemma

DOI10.4086/TOC.2019.V015A008MaRDI QIDQ5204826zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, Benjamin L. Edelman

Publication date 5 December 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1708.01646

zbMATH Keywords

additive combinatoricsalgebraic complexityarithmetic circuitscircuit complexitycomplexity theoryHamming distancelower boundsmatrix rigiditypolynomial methodpolynomialsrank

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) Special matrices (15B99) Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05)

Abstract: Matrix rigidity is a notion put forth by Valiant 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 efforts, no explicit matrix rigid enough to carry out Valiant's plan has been found. Recently, Alman and Williams showed, contrary to common belief, that the $2^{n}imes{2}^n$ Hadamard matrix could not be used for Valiant's program as it is not sufficiently rigid. In this note we observe a similar `non rigidity' phenomena for any $q^{n}imes{q}^n$ matrix $M$ of the form $M(x,y)=f(x+y)$, where $f:F_q^{n}o{F}_q$ is any function and $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 which is also the main ingredient in the recent solution of the cap-set problem.

Recommendations

• Theory and Applications of Models of Computation
• Fourier and circulant matrices are not rigid
• Probabilistic rank and matrix rigidity
• Matrix rigidity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity

Cited in

(11)

• Lower bounds for matrix factorization
• Strictly positive real matrices and the Lefschetz-Kalman-Yakubovich lemma
• New applications of the polynomial method: the cap set conjecture and beyond
• Fourier and circulant matrices are not rigid
• Lower bounds for matrix factorization
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)
• Fourier and circulant matrices are not rigid
• Rigid matrices from rectangular PCPs
• Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
• Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
• Kronecker products, low-depth circuits, and matrix rigidity

This page was built for publication: Matrix rigidity and the Croot-Lev-Pach lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204826)