30 stycznia 2018 10:15
[Seminarium ZOK] Meesum Syed Mohammad: "Matrix Rigidity from the Viewpoint of Parameterized Complexity"
Tytuł: Matrix Rigidity from the Viewpoint of Parameterized Complexity
Autorzy: Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh and Meirav Zehavi
Prelegent: Syed Mohammad Meesum
Czas i miejsce: wtorek, 30-go stycznia 2018, 10:15, sala 310.
Streszczenie:
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.