Tata Institute of Fundamental Research
Coloring, Embedding, Compression and Data Structure Problems on Uniform Hypergraphs
Synopsis Seminar
Speaker:
Saswata Shannigrahi
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha R
Date:
Tuesday, 11 Jan 2011 (all day)
Venue:
AG-69
(Scan to add to calendar)
Abstract:
We study four problems on uniform hypergraph. First, we present a streaming algorithm for two-coloring uniform hypergraphs with limited number of hyperedges. Second, we show relationships between four different geometric parameters of the embedding of a complete 3-uniform hypergraph in 3-dimensional space. Third, we present a compression scheme for uniform hypertrees, which are generalizations of trees. Finally, we present a data structure for succinctly storing a hyperedge of a complete uniform hypergraph in order to support membership queries in the bitprobe model.
| Speaker: | Saswata Shannigrahi Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha R |
| Date: | Tuesday, 11 Jan 2011 (all day) |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
We study four problems on uniform hypergraph. First, we present a streaming algorithm for two-coloring uniform hypergraphs with limited number of hyperedges. Second, we show relationships between four different geometric parameters of the embedding of a complete 3-uniform hypergraph in 3-dimensional space. Third, we present a compression scheme for uniform hypertrees, which are generalizations of trees. Finally, we present a data structure for succinctly storing a hyperedge of a complete uniform hypergraph in order to support membership queries in the bitprobe model.