DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.68

Improved Upper Bounds for the Rigidity of Kronecker Products

Authors: Bohdan Kivva

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

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 (Valiant-rigid) still remains open. Moreover, since 2017 most of the long-studied candidates have been shown not to be Valiant-rigid. Some of those former candidates for rigidity are Kronecker products of small matrices. In a recent paper (STOC'21), Alman gave a general non-rigidity 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 Valiant-rigid; these now include the Kronecker products of Paley-Hadamard matrices and Hadamard matrices of bounded size.

Cite as

Bohdan Kivva. Improved Upper Bounds for the Rigidity of Kronecker Products. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.68},
  URN =		{urn:nbn:de:0030-drops-145081},
  doi =		{10.4230/LIPIcs.MFCS.2021.68},
  annote =	{Keywords: Matrix rigidity, Kronecker product, Hadamard matrices}
}

Document

DOI: 10.4230/LIPIcs.CCC.2021.41

Matrix Rigidity Depends on the Target Field

Authors: László Babai and Bohdan Kivva

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

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 (Valiant, 1977). We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2-o(1) between strict and absolute rigidities. The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments. Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over 𝔽₂.

Cite as

László Babai and Bohdan Kivva. Matrix Rigidity Depends on the Target Field. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.CCC.2021.41,
  author =	{Babai, L\'{a}szl\'{o} and Kivva, Bohdan},
  title =	{{Matrix Rigidity Depends on the Target Field}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{41:1--41:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.41},
  URN =		{urn:nbn:de:0030-drops-143153},
  doi =		{10.4230/LIPIcs.CCC.2021.41},
  annote =	{Keywords: Matrix rigidity, field extension}
}

Search Results

Documents authored by Kivva, Bohdan

Improved Upper Bounds for the Rigidity of Kronecker Products

Abstract

Cite as

Matrix Rigidity Depends on the Target Field

Abstract

Cite as

Thanks for your feedback!

Could not send message