Matrix Rigidity Upper Bounds Tutorial by Josh Alman

Tutorial on Matrix Rigidity Upper Bounds Josh Alman (Harvard) FSTTCS 2020 Workshop on Matrix Rigidity

Matrix Rigidity Matrix ? is rigid if it is far from any low-rank matrix (in Hamming dist) ?? = minimum # of entries one needs to change in ? to make its rank ? E.g. if ??is the ? ? identity matrix, then for all ?, ??? = ? ? ? ?is very rigid with high probability: Random ? ? matrix ?? ?2 ??? = (?2) for ? = ?(?)

Matrix Rigidity ?? = minimum # of entries one needs to change in ? to make its rank ? First introduced by [L. Valiant 77] to study arithmetic circuits [L. Valiant 77] Every ? ?? ? computable by ?(?)-size ?(log ?)-depth arithmetic circuits has, for all ? > 0, ? < ?1+?. ? ? loglog? A random matrix is rigid w.h.p.; goal to show some explicit family of matrices is rigid This talk: techniques for showing that matrices are not rigid

Two Techniques 1. Diagonalization If ? is non-rigid, then for any diagonal matrix ?, the matrix ??? is non-rigid 2. The polynomial method If a low-degree polynomial computes most entries of matrix ?, then ? is non-rigid Results I ll discuss today: [A-Williams 17]: Walsh-Hadamard transform (plus a new generalization!) [Dvir-Edelman 17]: ? ?,? = ?(? + ?) for ?,? ?? [Dvir-Liu 19]: Fourier, Circulant, Group Algebra matrices ? Other non-rigidity techniques that I won t talk about today (see Sasha s talk)

Technique 1: Diagonalization If ? is non-rigid, then for any diagonal matrix ?, the matrix ??? is non-rigid

Products of Non-Rigid Matrices ??? ? Lemma: If ?,? are matrices with ? and ? ? ? Proof: We can write ? = ??+ ??, ? = ??+ ?? where ???? ?? and ???? ?? are both ?, and ??,?? each have ? nonzero entries in each row and column ?? ?? has ?2 nonzero entries in each row and column ??? = minimum ? such that one ? can change at most ? entries in each row and column of ? to make its rank at most ? E.g. for the identity matrix ??, we have ?? ??? ?, then ?? 2? ?2 ??0 = 1 Corollary: If ?,? are not (rc) Valiant- rigid, then neither is ? ?. If ? > 0, ? and ? ???(?/loglog ?) ?? ???(?/loglog ?) ?? ? ? = ??+ ?? ??+ ?? = ?? ??+ ?? + ?? ??+ ?? ?? ?? ?(?/loglog ?) ?2? Then ? ?

Technique 1: Diagonalization If ? is not Valiant-rigid, then for every diagonal matrix ?, the matrix ? ? ? is also not rigid As we ll see soon, many well-studied matrices ? (e.g. Walsh- Hadamard, Fourier, Disjointness) diagonalize large, important families of matrices Could be a tool for proving a matrix ? is rigid Just need to show there exists a ? such that ? ? ? is rigid We will instead use this as a tool for proving that large classes of matrices are not rigid

Walsh-Hadamard Transform ?? ?? ?? ?? ?1=1 1 1 , ??+1= ? 1 1 Let ? = 2?, so ?? ?? ? ?? has a ?(?log?)-size, ?(log?)-depth linear circuit Believed to be optimal One avenue toward proving this: Show that ?? is Valiant-rigid Theorem [A-Williams 17]: For every field ? and every ? > 0, the matrix ?? is not Valiant-rigid: ???1 (?2/ log 1/?)= ?(??) ??

?? ?? ?? ?? OR, AND Matrix For any field ? and any function ?: 0,1? ? Define OR matrix ?? For ?,? 0,1?: ?? ??+1= ?2? 2?, and the AND matrix ?? ?2? 2? by ?,? = ? ? ? , ?,? = ? ? ? ?? For ? 0,1?: ?????? ? = 1 ?=1 E.g. ?? is an AND matrix ??????? ? can also be much more complicated! Any AND matrix is a permutation of the rows+cols of an OR matrix (and vice versa) ? ?? is not Valiant-rigid: Theorem: For every ? and every ? > 0, the matrix ?? ???1 (?2/ log 1/?)= ?(??) ??

Diagonalizing AND Matrix with Disjointness ?? is the disjointness matrix: ?1=1 1 ??= ???? ??[?,?] = 1 if ?,? = 0, 0 if ?,? > 0. For any field ?, function ?: 0,1? ?, and ?,? 0,1?: ?? ?? 0 0 1, ??+1= ? 1 ?? ?,? = ? ? ? ?? There exists a diagonal matrix ?? ?2? 2? such that ?? is not rigid: Goals toward proving ?? 1. Prove that this factorization is true 2. Prove that ?? is not Valiant-rigid = ?? ?? ??

For ?,? 0,1? and diagonal 2? 2?matrix ?: ?? diagonalizes ?? For ?,? 0,1?: ?? ???,? = ??? ? ? ? ?2? with ? = ????(?). ??????,? = ???,? ? ?,? ??[?,?] ? 0,1? ?,? = ? ? ? = ? ?,? ? 0,1? ??? ? ? =??? ? ? =1 Define ??,? ?2? by ??? = ?(?), and ? = ?? = ? ?,? 1??. ? 0,1? ? ? ? =1 ??? = ??[? ?,?]? ?,? = ??? ?,? ?[?] ? 0,1? = ??? [? ?] = ??[? ?] = ?(? ?) = ?? ? 0,1? [?,?]

???,? = ??? ? ? Proof that ?? is not rigid ? ? Lemma: For any positive integer ?, we can remove so that each row or column has at most ? ? <? columns of ?? <? rows and ? nonzero entries. Proof: Remove the rows corresponding to ? 0,1? with ? > ? ?, and columns corresponding to ? 0,1? with ? > ? ? Let ?be a row we didn t remove, so ? ? ?. How many ? are there that we didn t remove (i.e. ? ? ?) with ??? ? ? = 1? Each ? with ? ? = 0 must have ? ? = 1. There are ? ? coordinates ? with ? ? = 1, and we need to pick ? of them to have ? ? = 0. Thus, at most ? ? ? nonzero entries (i.e. such choices of ?) in row ?.

???,? = ??? ? ? Proof that ?? is not rigid ? ? Lemma: For any positive integer ?, we can remove so that each row or column has at most ? ? <? columns of ?? <? rows and ? nonzero entries. Theorem: For every field ? and every ? > 0, ???1 (?2/ log 1/?)= ?(??) ?? 1 2 ? ?. Proof: Set ? = ? ?1 (?2/ log 1/?) rows and columns ? Can remove 2 <?= 2 1 2 ? ? < Removing one row or column changes the rank by at most 1! To make the number of nonzero entries in each row/column at most 1 2+ ? ? 1 2 ? ? 1 2+ ? ? ? ? ? ? ? ?(??) = =

Technique 2: Polynomial Method If a low-degree polynomial computes most entries of matrix ?, then ? is non-rigid

Technique 2: Polynomial Method ? ??, Theorem [Dvir-Edelman 19]: For any finite field ?? and function ?:?? the matrix ? ?? ? ?,? = ? ? + ? , is not Valiant-rigid. ?? ?? given by, for ?,? ?? ?, (Note: later work [Dvir-Liu 19] generalized this result; I will discuss this later) Proof outline: 1. The function ? ? + ? has a low-degree polynomial approximation 2. This implies that ? is not Valiant-rigid

Monomials of multivariate polynomials over ?? ?? ?1 ?? Let ??,?,? the number of degree ? monomials in ? variables over ?? No variable in a poly over ??needs to be taken to a power higher than ? 1 ?1 | 0 ?? ? 1, ?1+ + ?? ? , For fixed ? and large ?, the number of degree-?monomials is like a normal curve concentrated around ? = ?(? 1)/2. E.g. for ? = 2, we have ??,?,2= ? ?

Technique 2: Polynomial Method Remark: Matrix ? has rank ? if and only if there are functions ?1, ,??,?1, ,?? such that, for every row ? and column ?, ? ? ?,? = ??? ??? . ?=1 ?? ?? given by 2? ?? is a degree-? polynomial, then ? ?? Lemma: If ?:?? ? ?,? = ?(?,?) has rank ?2?,?,? Proof: ? ?1, ,??,?1, ,?? is a sum of ?2?,?,? monomials. Each monomial is of the form ? ? ?(?) E.g. 3?1?5?2 3?11?13= 3?1?5 (?2 3?11?13)

Technique 2: Polynomial Method 2? ?? is a degree-? polynomial, then Lemma [Croot-Lev-Pach 17]: If ?:?? ? ?? ?? ?? given by ? ?,? = ?(?,?) has rank 2 ??, ? Proof: In every monomial of degree ?, at least one of the ? part and the ? part has degree 2 Can group together monomials with the same low-degree ? part or ? part into the same ? ? ?(?) term E.g. 3?1?5?2 = (?1?5)(3?2 2 ,? ? 3?11?13+ 2?1?5?4 8?5?11+ 6?1?5?1?2?3?4 3?11?13+ 2?4 8?5?11+ 6?1?2?3?4) ? 2, Only need ??, ? and ??, ? 2 ,? terms for each ? part of degree 2 ,? terms for each ? part of degree ? 2

?(? + ?) as a polynomial, first attempt ? ??, Theorem [Dvir-Edelman 19]: For any finite field ?? and function ?:?? the matrix ? ?? ? ?,? = ? ? + ? , is not Valiant-rigid. ?? ?? given by, for ?,? ?? ?, ? ?? can be written as a polynomial of degree ?(? 1). ,?= ?? (trivial) Any ?:?? Therefore, ? has rank 2 ??,?(? 1) Idea: find a lower degree polynomial which usually agrees with ? 2

Approximating ? by a low-degree polynomial ? ??, and degree ?, there is a ?:?? ? ?? Lemma: For any ?:?? such that ? has degree ?, and ? and ? agree on at least ??,?,? inputs Proof: Consider the ?? ??,?,? matrix that maps the coefficients of a degree ? polynomial to its ?? outputs. The columns are linearly independent Thus, there s a full rank ??,?,? ??,?,? submatrix. Let ? be the set of rows in this submatrix. We can thus pick coefficients for the monomials of degree ? that make the outputs on ? any values we want

Putting everything together ? ??, and degree ?, ? ?? such that 2? ?? is ?? ?? given Lemma 1: For any ?:?? there is a ?:?? ? has degree ?, and ? and ? agree on at least ??,?,? inputs Lemma 2 [Croot-Lev-Pach 17]: If ?:?? a degree-? polynomial, then ? ?? by ? ?,? = ?(?,?) has rank 2 ??, ? 2 ,? ? ??, the Theorem [Dvir-Edelman 19]: For any finite field ?? and function ?:?? matrix ? ?? ?? ?? given by, for ?,? ?? ?, ? ?,? = ? ? + ? , is not Valiant-rigid. Proof: Apply Lemma 1 with ? = 1 ? ?(? 1). Lemma 1: # of entries per row/col where matrix ? ?,? = ?(? + ?) disagrees with ? is ??,? ? ? 1 ,? ???. Lemma 2: the rank of ? is 2 ??,1 21 ? ? ? 1 ,? ?1 ? ?. ???1 ? ? ??? Thus, ?

What other matrices are not rigid? [Dvir-Liu 19]: The following are not Valiant-rigid: Any Fourier transform ? ? 2?? ? Matrix ?? ? ? given by, for ?,? {0,1, ,? 1}, ???,? = ? Any group algebra matrix over any field for finite abelian group ? For any ?:? ?, matrix ??,? ?? |?| given by ??,??,? = ?(? ?). Includes [Dvir-Edelman 19] matrices, circulant matrices, etc What s next? Rule out non-abelian groups ?? [Dvir-Liu 19]: Quasi-random groups? Non-rigidity in other parameter settings? E.g. Razborov-rigidity upper bounds? More applications of non-rigidity? Use these techniques to narrow in on candidate rigid matrices?