Jan. 30, 2018, 10:15 a.m.
[COG Seminar] Meesum Syed Mohammad: "Matrix Rigidity from the Viewpoint of Parameterized Complexity"
Title: Matrix Rigidity from the Viewpoint of Parameterized Complexity
Authors: Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh and Meirav Zehavi
Speaker: Syed Mohammad Meesum
Time and place: Tuesday, 30th of January, 2018, 10:15 am, room 310.
Abstract:
We will consider the following problem,
Input: A matrix M over some field F and integers r,k.
Parameter: r,k
Question: Can we alter at most k entries in M such that rank of the edited matrix becomes at most r ?
We study the question for an arbitrary matrix over a given field F, where F is either a finite prime sized field or the field of reals. This problem corresponds to the decision version of the classical matrix rigidity problem. We considered the parameter to be r+k. We showed that this problem is fixed parameter tractable wrt r+k. We also show that this problem is W[1] hard with respect to k, i.e. it does not admit any algorithm of the form f(k) * poly(input size) under some widely held assumptions.
Appeared in STACS 2017.