I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https://arxiv.org/abs/1103.6073.

As far as I understand, $f:[n] \rightarrow [N]$ is a hash function, that should be picked uniformly at random out of a pairwise independent hash functions family $H$. I have a few general questions:

  1. Does the space complexity required by $f$ is affected by the fact that $H$ is $k$-wise independent? Why? (If it does, then also- how?)
  2. What do we know about $|H|$? What if $H$ is $k$-wise independent?
  3. Is there a more space-efficient way to store $f$ than storing an $N \times m$ matrix that maps each vertex to its color, using O($N m$) storage words?
  4. Does the total space complexity which is required in order to use $f$ as described in the paper is $|H| \cdot O(\text{space complexity of storing } f)$?

Best regards


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.