Hypergraph Two-Coloring in the Streaming Model

We consider space-efficient algorithms for two-coloring $n$-uniform hypergraphs $H=(V,E)$ in the streaming model, when the hyperedges arrive one at a time. It is known that any such hypergraph with at most $0.7 \sqrt{\frac{n}{\ln n}} 2^n$ hyperedges has a two-coloring [Radhakrishnan & Srinivasan, RSA, 2000], which can be found deterministically in polynomial time, if allowed full access to the input.

1. Let $s^D(v,q,n)$ be the minimum space used by a deterministic one-pass streaming algorithm that on receiving an $n$-uniform hypergraph $H$ on $v$ vertices and $q$ hyperedges produces a proper two-coloring of $H$. We show that $s^D(n^2,q,n)=\mathrm{\Omega }(q\mathrm{/}n)$ when $q\le 0.7\sqrt{\frac{n}{\ln n}}{2}^n$, and $s^D(n^2,q,n)=\mathrm{\Omega }(\sqrt{\frac{1}{n\ln n}}{2}^n)$ otherwise.
2. Let $s^R(v,q,n)$ be the minimum space used by a randomized one-pass streaming algorithm that on receiving an $n$-uniform hypergraph $H$ on $v$ vertices and $q$ hyperedges with high probability produces a proper two-coloring of $H$ (or declares failure). We show that $s^R(v, \frac{1}{10}\sqrt{\frac{n}{\ln n}} 2^n, n) = O(v \log v)$ by giving an efficient randomized streaming algorithm. The above results are inspired by the study of the number $q(n)$, the minimum possible number of hyperedges in a $n$-uniform hypergraph that is not two-colorable. It is known that $q(n)=\mathrm{\Omega }(\sqrt{\frac{n}{\ln n}})$ [Radhakrishnan-Srinivasan] and $q(n)=O(n^2{2}^n)$ [Erdos, 1963]. Our first result shows that no space-efficient deterministic streaming algorithm can match the performance of the offline algorithm of Radhakrishnan and Srinivasan; the second result shows that there is, however, a space-efficient randomized streaming algorithm for the task.