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.