Title: Streaming Algorithm for two coloring uniform hypergraphs
Abstract: Two colorability of uniform hypergraphs , also called Property B,
is a well-studied problem in hypergraph theory. Radhakrishnan and Srinivasan
[FOCS 1998] showed that any n-uniform hypergraph (V,E) with at most
O(sqrt(n/ln n) 2 ^n) hyperedges can be 2-colored. In the same paper, they
also provided an efficient (requiring polynomial time in the size of the
input) randomized algorithm that produces such a coloring . However, this
algorithm requires random access to the hyperedge set of the input hypergraph.
It can be noted that the number of hyperedges in a hypergraph can be
superpolynomial in |V|, and it is not feasible to store the entire hypergraph
in random-access memory (RAM). In this talk, we will first present a variant
of the above algorithm that can be implemented in the streaming model (with
just one pass over the input), using O(|V|B) RAM space, where V is the vertex
set of the hypergraph and each vertex is represented by B bits.