This paper says "For k ≥ 7, k-Dominating Set can be solved in nk+o(1) time.",
but Reference 17 only makes that claim for ​ ℓ ≥ 8 , ​ and it seems like on the
"Proposition 2" page, the matrices would actually have height ​ $\binom{n}{\hspace{-0.02 in}\lceil k/2\rceil \hspace{.02 in}}$ ​ and ​ $\binom{n}{\hspace{-0.02 in}\lfloor k/2\rfloor \hspace{.02 in}}$ .
(I asked Ryan Williams about this 3 days ago and he hasn't responded yet.)

  • $\begingroup$ If the obvious bound you get from applying the fastest known rectangular matrix multiplication alg (currently LeGall's) doesn't yield the result, then it's a typo/mistake. $\endgroup$ Jan 6, 2016 at 8:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.