Before revision:  On the hardness side, we show a \Omega (n^2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the k-tuple dominating set problem.
After revision:  On the hardness side, we show a \Omega (n^2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the -tuple dominating set problem.