Document Open Access Logo

Matrix Rigidity from the Viewpoint of Parameterized Complexity

Authors Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.32.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Fedor V. Fomin
Daniel Lokshtanov
S. M. Meesum
Saket Saurabh
Meirav Zehavi

Cite AsGet BibTex

Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi. Matrix Rigidity from the Viewpoint of Parameterized Complexity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.32

Abstract

The rigidity of a matrix A for a target rank r over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational Complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of Parameterized Complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of Parameterized Complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in case F equals the reals or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in Real Algebraic Geometry, which are not well known in Parameterized Complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.
Keywords
  • Matrix Rigidity
  • Parameterized Complexity
  • Linear Algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. Google Scholar
  2. E. Bonnet, L. Egri, and D. Marx. Fixed-parameter approximability of boolean MinCSPs. In ESA, pages 18:1-18:18, 2016. Google Scholar
  3. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  4. Amit Jayant Deshpande. Sampling-based algorithms for dimension reduction. PhD thesis, Massachusetts Institute of Technology, 2007. Google Scholar
  5. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  6. Joel Friedman. A note on matrix rigidity. Combinatorica, 13(2):235-239, 1993. Google Scholar
  7. D. Grigoriev. Using the notions of separability and independence for proving the lower bounds on the circuit complexity (in russian). Notes of the Leningrad branch of the Steklov Mathematical Institute, Nauka, 1976. Google Scholar
  8. D. Grigoriev. Using the notions of separability and independence for proving the lower bounds on the circuit complexity. Journal of Soviet Math., 14(5):1450-1456, 1980. Google Scholar
  9. Neeraj Kayal. Solvability of a system of bivariate polynomial equations over a finite field. In ICALP, pages 551-562, 2005. Google Scholar
  10. Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and Jayalal M. N. Sarma. Using elimination theory to construct rigid matrices. Computational Complexity, 23(4):531-563, 2013. Google Scholar
  11. Kenneth Lange. Hadamard’s determinant inequality. The American Mathematical Monthly, 121(3):258-259, 2014. Google Scholar
  12. Satyanarayana V. Lokam. On the rigidity of Vandermonde matrices. Theoretical Computer Science, 237(1–2):477-483, 2000. Google Scholar
  13. Satyanarayana V. Lokam. Complexity lower bounds using linear algebra. Found. Trends Theor. Comput. Sci., 4:1-155, January 2009. Google Scholar
  14. S. V. Lokam. Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity. In FOCS, pages 6-15, 1995. Google Scholar
  15. Meena Mahajan and Jayalal M. N. Sarma. On the complexity of matrix rank and rigidity. In CSR, pages 269-280, 2007. Google Scholar
  16. S. M. Meesum, Pranabendu Misra, and Saket Saurabh. Reducing rank of the adjacency matrix by graph modification. In COCOON, pages 361-373, 2015. Google Scholar
  17. S. M. Meesum and S. Saurabh. Rank reduction of directed graphs by vertex and edge deletions. In LATIN, pages 619-633, 2016. Google Scholar
  18. A. A. Razborov. On rigid matrices. Manuscript in russian, 1989. Google Scholar
  19. Jayalal M. N. Sarma. Complexity Theoretic Aspects of Rank, Rigidity and Circuit Evaluation. PhD thesis, The Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai, 2009. Google Scholar
  20. M. A. Shokrollahi, D. Spielman, and V. Stemann. A remark on matrix rigidity. Information Processing Letters, 64(6):283-285, 1997. Google Scholar
  21. L. E. Sigler. Algebra. Undergraduate Texts in Mathematics. Springer-Verlag, 1976. Google Scholar
  22. L. G. Valiant. Graph-theoretic arguments in low-level complexity. In MFCS, pages 162-176, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact