Hypergraph Two-Coloring in the Streaming Model

Jaikumar Radhakrishnan, Saswata Shannigrahi, Rakesh Venkat

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 suc…