{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:03Z","timestamp":1787321103591,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>For a target rank $r$, the rigidity of a matrix $A$ over a field $\\mathbb{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 the case $\\mathbb{F}=\\mathbb{R}$ or $\\mathbb{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 \\sf W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.<\/jats:p>","DOI":"10.1137\/17m112258x","type":"journal-article","created":{"date-parts":[[2018,5,1]],"date-time":"2018-05-01T11:17:06Z","timestamp":1525173426000},"page":"966-985","source":"Crossref","is-referenced-by-count":4,"title":["Matrix Rigidity from the Viewpoint of Parameterized Complexity"],"prefix":"10.1137","volume":"32","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. M.","family":"Meesum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,1]]},"reference":[{"key":"atypb1","first-page":"18","author":"Bonnet E.","year":"2016","journal-title":"Proceedings of ESA"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb3","first-page":"249","author":"Damaschke P.","year":"2014","journal-title":"Proceedings of WALCOM"},{"key":"atypb4","unstructured":"A. J. Deshpande,\n                      Sampling-Based Algorithms for Dimension Reduction\n                      , Ph.D. thesis, Massachusetts Institute of Technology, 2007."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303207"},{"key":"atypb7","unstructured":"D. Grigoriev,\n                      Using the Notions of Separability and Independence for Proving the Lower Bounds on the Circuit Complexity\n                      , Notes to Leningrad Branch of the Steklov Mathematical Institute, Nauka, 1976 (in Russian)."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01693976"},{"key":"atypb9","first-page":"551","author":"Kayal N.","year":"2005","journal-title":"Proceedings of ICALP"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0061-0"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.4169\/amer.math.monthly.121.03.258"},{"key":"atypb12","first-page":"6","author":"Lokam S. V.","year":"1995","journal-title":"Proceedings of FOCS"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00008-6"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1561\/0400000011"},{"key":"atypb15","first-page":"269","author":"Mahajan M.","year":"2007","journal-title":"Proceedings of CSR"},{"key":"atypb16","first-page":"361","author":"Meesum S. M.","year":"2015","journal-title":"Proceedings of COCOON"},{"key":"atypb17","first-page":"1","author":"Meesum S. M.","year":"2017","journal-title":"Algorithmica"},{"key":"atypb18","unstructured":"A. A. Razborov,\n                      On Rigid Matrices\n                      , manuscript, 1989 (in Russian)."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"atypb20","unstructured":"J. Sarma M.N.\n                      Complexity Theoretic Aspects of Rank, Rigidity and Circuit Evaluation\n                      , Ph.D. thesis, The Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai, 2009."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00190-7"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"L. Sigler,\n                      Algebra\n                      , Undergrad. Texts Math., Springer, New York, 1976.","DOI":"10.1007\/978-1-4613-9410-5"},{"key":"atypb23","first-page":"162","author":"Valiant L. G.","year":"1977","journal-title":"Proceedings of MFCS"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M112258X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:40Z","timestamp":1787317540000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M112258X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M112258X"],"URL":"https:\/\/doi.org\/10.1137\/17m112258x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}