Kivva, Bohdan
Improved Upper Bounds for the Rigidity of Kronecker Products
Abstract
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r. At MFCS'77, Valiant introduced matrix rigidity as a tool to prove circuit lower bounds for linear functions and since then this notion received much attention and found applications in other areas of complexity theory. The problem of constructing an explicit family of matrices that are sufficiently rigid for Valiant’s reduction (Valiantrigid) still remains open. Moreover, since 2017 most of the longstudied candidates have been shown not to be Valiantrigid.
Some of those former candidates for rigidity are Kronecker products of small matrices. In a recent paper (STOC'21), Alman gave a general nonrigidity result for such matrices: he showed that if an n× n matrix A (over any field) is a Kronecker product of d× d matrices M₁,… ,M_k (so n = d^k) (d ≥ 2) then changing only n^{1+ε} entries of A one can reduce its rank to ≤ n^{1γ}, where 1/γ is roughly 2^d/ε².
In this note we improve this result in two directions. First, we do not require the matrices M_i to have equal size. Second, we reduce 1/γ from exponential in d to roughly d^{3/2}/ε² (where d is the maximum size of the matrices M_i), and to nearly linear (roughly d/ε²) for matrices M_i of sizes within a constant factor of each other.
As an application of our results we significantly expand the class of Hadamard matrices that are known not to be Valiantrigid; these now include the Kronecker products of PaleyHadamard matrices and Hadamard matrices of bounded size.
BibTeX  Entry
@InProceedings{kivva:LIPIcs.MFCS.2021.68,
author = {Kivva, Bohdan},
title = {{Improved Upper Bounds for the Rigidity of Kronecker Products}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {68:168:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14508},
URN = {urn:nbn:de:0030drops145081},
doi = {10.4230/LIPIcs.MFCS.2021.68},
annote = {Keywords: Matrix rigidity, Kronecker product, Hadamard matrices}
}
18.08.2021
Keywords: 

Matrix rigidity, Kronecker product, Hadamard matrices 
Seminar: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Issue date: 

2021 
Date of publication: 

18.08.2021 