Abstract:
A long-standing assumption common in algorithm design is that any part of the input is accessible at any time for unit cost. However, as we work with increasingly large data sets, or as we build smaller devices, we must revisit this assumption. In this talk, I survey some of my work on graph algorithms designed for circumstances where traditional assumptions about inputs do not apply.
1. Classical graph algorithms require direct access to the input graph and this is not feasible when the graph is too large to fit in memory. For computation on massive graphs we consider the dynamic streaming graph model. Given an input graph defined by as a stream of edge insertions and deletions, our goal is to approximate properties of this graph using space sublinear in the size of the stream. In this talk, I will present algorithms for approximating vertex connectivity and hypergraph edge connectivity in graph streams.
2. In certain applications the input graph is not explicitly represented, but its edges may be discovered via queries which require costly computation or measurement. I will present Mesh, a memory manager which compacts memory efficiently by finding an approximate graph matching subject to stringent time and edge query restrictions.
Advisor: Andrew McGregor