We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on @math vertices up to a @math error must use @math bits of space in the worst case, improving the @math bound of and matching the best known upper bound achieved by spectral sparsifiers. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two @math regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.
The paper @cite_1 also studied the problem of producing a for each'' sketching algorithm, which has the property that for any particular query @math , @math approximates @math with constant probability. They showed that in this weaker model it is possible to obtain @math cut sketches of size @math and @math -spectral sketches of size @math . The latter bound was recently improved to @math and generalized to include queries to the pseudoinverse in @cite_4 . In contrast, in this paper we study only the for all'' model, in which the sketch is required to work for all queries simultaneously.
@cite_1 @cite_4
2950897836 2765335021
We undertake a systematic study of sketching a quadratic form: given an @math matrix @math , create a succinct sketch @math which can produce (without further access to @math ) a multiplicative @math -approximation to @math for any desired query @math . While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size @math , via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query @math , with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all @math 's simultaneously, again there are no non-trivial sketches.) We design significantly better sketches for the important subclass of graph Laplacian matrices, which we also extend to symmetric diagonally dominant matrices. A sequence of work culminating in that of Batson, Spielman, and Srivastava (SIAM Review, 2014), shows that by choosing and reweighting @math edges in a graph, one achieves the "for all" guarantee. Our main results advance this front. @math For the "for all" guarantee, we prove that 's bound is optimal even when we restrict to "cut queries" @math . In contrast, previous lower bounds showed the bound only for spectral-sparsifiers . @math For the "for each" guarantee, we design a sketch of size @math bits for "cut queries" @math . We prove a nearly-matching lower bound of @math bits. For general queries @math , we construct sketches of size @math bits. In this paper we consider the problem of efficiently computing @math -sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance @math , we seek to construct a function @math such that for any vector @math (chosen obliviously from @math ), with high probability @math where @math is either the Laplacian or its pseudoinverse. Our goal is to construct such a sketch @math efficiently and to store it in the least space possible. We provide nearly-linear time algorithms that, when given a Laplacian matrix @math and an error tolerance @math , produce @math -size sketches of both @math and its pseudoinverse. Our algorithms improve upon the previous best sketch size of @math for sketching the Laplacian form by (2015) and @math for sketching the Laplacian pseudoinverse by Batson, Spielman, and Srivastava (2008). Furthermore we show how to compute all-pairs effective resistances from @math size sketch in @math time. This improves upon the previous best running time of @math by Spielman and Srivastava (2008).