The Sketching Complexity of Graph Cuts
Event details
| Date | 20.01.2015 |
| Hour | 16:00 › 17:00 |
| Speaker | Robert Krauthgamer, Professor, Weizmann Institute of Science |
| Location | |
| Category | Conferences - Seminars |
Abstract:
We study the problem of sketching an input graph $G$ on $n$ vertices, so that given (only) the sketch, one can estimate the weight (capacity) of any cut in the graph within a small approximation factor $1+\epsilon$. The classic cut-sparsifier construction of Benczur and Karger (STOC 1996) implies a sketch of size $\tilde O(n/\epsilon^2)$ [this notation hides logarithmic factors].
We show that the dependence on $\epsilon$ can be brought down to linear, at the price of achieving a slightly relaxed guarantee. Specifically, we design a randomized scheme that produces from $G$ a sketch of size $\tilde O(n/\epsilon)$ bits, from which the weight of any cut $(S,\bar S)$ can be reported, with high probability, within factor $1+\epsilon$. We also demonstrate some applications where this "for each" guarantee is indeed useful.
We further prove that that our relaxation is necessary. Specifically, a sketch that can $(1+\epsilon)$-approximate the weight of all cuts in the graph simultaneously (a so-called "for all" guarantee instead of "for each"), must be of size $\Omega(n/\epsilon^2)$ bits.
Joint work with Alexandr Andoni and David Woodruff.
We study the problem of sketching an input graph $G$ on $n$ vertices, so that given (only) the sketch, one can estimate the weight (capacity) of any cut in the graph within a small approximation factor $1+\epsilon$. The classic cut-sparsifier construction of Benczur and Karger (STOC 1996) implies a sketch of size $\tilde O(n/\epsilon^2)$ [this notation hides logarithmic factors].
We show that the dependence on $\epsilon$ can be brought down to linear, at the price of achieving a slightly relaxed guarantee. Specifically, we design a randomized scheme that produces from $G$ a sketch of size $\tilde O(n/\epsilon)$ bits, from which the weight of any cut $(S,\bar S)$ can be reported, with high probability, within factor $1+\epsilon$. We also demonstrate some applications where this "for each" guarantee is indeed useful.
We further prove that that our relaxation is necessary. Specifically, a sketch that can $(1+\epsilon)$-approximate the weight of all cuts in the graph simultaneously (a so-called "for all" guarantee instead of "for each"), must be of size $\Omega(n/\epsilon^2)$ bits.
Joint work with Alexandr Andoni and David Woodruff.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi