Seminar by Saswata Shannigrahi
Streaming algorithms for 2-coloring uniform hypergraphs
Saswata Shannigrahi
IIT Guwahati
Date: Saturday, August 25th, 2012
Time: 4PM
Venue: CS102.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 hypergraphin random-access memory (RAM). In this talk, we will 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. In addition, we will present a few related results.
(This is a joint work with Jaikumar Radhakrishnan, published in the Proceedings of WADS 2011)