Matrix rigidity and the croot-lev-pach lemma

Zeev Dvir, Benjamin L. Edelman

Research output: Contribution to journalArticle

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: Fnq → Fq is any function and Fq 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).

Original languageEnglish (US)
Pages (from-to)1-7
Number of pages7
JournalTheory of Computing
Volume15
DOIs
StatePublished - Jan 1 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Additive combinatorics
  • Algebraic complexity
  • Arithmetic circuits
  • Circuit complexity
  • Combinatorics
  • Complexity
  • Complexity theory
  • Hamming distance
  • Lower bounds
  • Matrix rigidity
  • Polynomial method
  • Polynomials
  • Rank

Fingerprint Dive into the research topics of 'Matrix rigidity and the croot-lev-pach lemma'. Together they form a unique fingerprint.

  • Cite this