×

Matrix rigidity from the viewpoint of parameterized complexity. (English) Zbl 1394.68177

Given an integer \(r>0\), the rigidity of a matrix \(A\) over a field \(\mathbb{F}\), denoted by \(\mathcal{R}^\mathbb{F}_A(r)\), is defined as the minimum Hamming distance between \(A\) and a matrix of rank at most \(r\); in other words, the minimum number of entries in \(A\) which one has to change in order to reduce its rank to at most \(r\). The rigidity of a matrix is a classical concept in computational complexity theory, and mainly used in graph theory. In this paper, by adapting the ideas from [S. M. Meesum et al., Lect. Notes Comput. Sci. 9198, 361–373 (2015; Zbl 1394.68268); S. M. Meesum and S. Saurabh, Lect. Notes Comput. Sci. 9644, 619–633 (2016; Zbl 1392.68329)], the authors analyze the rigidity of general matrices in the framework of parameterized complexity, and study the following problems:
Real Matrix Rigidity: Parameters: \(r\), \(k\). Input: A matrix \(A\) over the integers and two nonnegative integers \(r\), \(k\). Question: Is \(\mathcal{R}^\mathbb{R}_A(r)\leq k\)?
FF Matrix Rigidity: Parameters: \(p\), \(r\), \(k\). Input: A finite field \(\mathbb{F}_p\) of order \(p\), a matrix \(A\) over \(\mathbb{F}_p\), and two nonnegative integers \(r\), \(k\). Question: Is \(\mathcal{R}^{\mathbb{F}_p}_A(r)\leq k\)?
And the principal results are:
Theorem 4.4. Real Matrix Rigidity can be solved in \(\mathcal{O}^*(2^{\mathcal{O}(r\cdot k\cdot\log(r\cdot k))})\) time.
Theorem 4.6. FF Matrix Rigidity can be solved in \(\mathcal{O}^*(f(r,k))\) time for a function \(f\) that depends only on \(r\) and \(k\).
Theorem 5.1. FF Matrix Rigidityis solvable in time \(\mathcal{O}^*(2^{\mathcal{O}(f(r,p)\sqrt{k} \log k)})\) for some function \(f\) that depends only on \(r\) and \(p\).

MSC:

68Q25 Analysis of algorithms and problem complexity
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A03 Vector spaces, linear dependence, rank, lineability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Bonnet, L. Egri, and D. Marx, {\it Fixed-parameter approximability of boolean MinCSPs}, in Proceedings of ESA, 2016, 18. · Zbl 1397.68090
[2] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, {\it Parameterized Algorithms}, Springer, New York, 2015. · Zbl 1334.90001
[3] P. Damaschke and O. Mogren, {\it Editing simple graphs}, in Proceedings of WALCOM, 2014, pp. 249-260. · Zbl 1407.68350
[4] A. J. Deshpande, {\it Sampling-Based Algorithms for Dimension Reduction}, Ph.D. thesis, Massachusetts Institute of Technology, 2007. · Zbl 1232.68172
[5] R. G. Downey and M. R. Fellows, {\it Fundamentals of Parameterized Complexity}, Texts Comput. Sci., Springer, New York, 2013. · Zbl 1358.68006
[6] J. Friedman, {\it A note on matrix rigidity}, Combinatorica, 13 (1993), pp. 235-239. · Zbl 0848.15005
[7] D. Grigoriev, {\it Using the Notions of Separability and Independence for Proving the Lower Bounds on the Circuit Complexity}, Notes to Leningrad Branch of the Steklov Mathematical Institute, Nauka, 1976 (in Russian).
[8] D. Grigoriev, {\it Using the notions of separability and independence for proving the lower bounds on the circuit complexity}, J. Soviet Math., 14 (1980), pp. 1450-1456.
[9] N. Kayal, {\it Solvability of a system of bivariate polynomial equations over a finite field}, in Proceedings of ICALP, 2005, pp. 551-562. · Zbl 1084.11509
[10] A. Kumar, S. V. Lokam, V. M. Patankar, and M. N. J. Sarma, {\it Using elimination theory to construct rigid matrices}, Comput. Complexity, 23 (2013), pp. 531-563. · Zbl 1366.68076
[11] K. Lange, {\it Hadamards determinant inequality}, Amer. Math. Monthly, 121 (2014), pp. 258-259. · Zbl 1303.15009
[12] S. V. Lokam, {\it Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity}, in Proceedings of FOCS, 1995, pp. 6-15. · Zbl 0937.68515
[13] S. V. Lokam, {\it On the rigidity of Vandermonde matrices}, Theoret. Comput. Sci., 237 (2000), pp. 477-483. · Zbl 0943.68072
[14] S. V. Lokam, {\it Complexity lower bounds using linear algebra}, Found. Trends Theor. Comput. Sci., 4 (2009), pp. 1-155. · Zbl 1176.68084
[15] M. Mahajan and J. Sarma M.N., {\it On the complexity of matrix rank and rigidity}, in Proceedings of CSR, 2007, pp. 269-280. · Zbl 1188.68158
[16] S. M. Meesum, P. Misra, and S. Saurabh, {\it Reducing rank of the adjacency matrix by graph modification}, in Proceedings of COCOON, 2015, pp. 361-373. · Zbl 1394.68268
[17] S. M. Meesum and S. Saurabh, {\it Rank reduction of oriented graphs by vertex and edge deletions}, Algorithmica, 2017, pp. 1-20. · Zbl 1392.68329
[18] A. A. Razborov, {\it On Rigid Matrices}, manuscript, 1989 (in Russian). · Zbl 1522.03322
[19] J. Renegar, {\it On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals}, J. Symbolic Comput., 13 (1992), pp. 255-299. · Zbl 0763.68042
[20] J. Sarma M.N., {\it Complexity Theoretic Aspects of Rank, Rigidity and Circuit Evaluation}, Ph.D. thesis, The Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai, 2009.
[21] M. A. Shokrollahi, D. Spielman, and V. Stemann, {\it A remark on matrix rigidity}, Inform. Process. Lett., 64 (1997), pp. 283-285. · Zbl 1337.15004
[22] L. Sigler, {\it Algebra}, Undergrad. Texts Math., Springer, New York, 1976.
[23] L. G. Valiant, {\it Graph-theoretic arguments in low-level complexity}, in Proceedings of MFCS, 1977, pp. 162-176. · Zbl 0384.68046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.