  In this paper we consider the problem of efficiently computing
$\epsilon$-sketches for the Laplacian and its pseudoinverse. Given a Laplacian
and an error tolerance $\epsilon$, we seek to construct a function $f$ such
that for any vector $x$ (chosen obliviously from $f$), with high probability
$(1-\epsilon) x^\top A x \leq f(x) \leq (1 + \epsilon) x^\top A x$ where $A$ is
either the Laplacian or its pseudoinverse. Our goal is to construct such a
sketch $f$ efficiently and to store it in the least space possible.
  We provide nearly-linear time algorithms that, when given a Laplacian matrix
$\mathcal{L} \in \mathbb{R}^{n \times n}$ and an error tolerance $\epsilon$,
produce $\tilde{O}(n/\epsilon)$-size sketches of both $\mathcal{L}$ and its
pseudoinverse. Our algorithms improve upon the previous best sketch size of
$\widetilde{O}(n / \epsilon^{1.6})$ for sketching the Laplacian form by Andoni
et al (2015) and $O(n / \epsilon^2)$ for sketching the Laplacian pseudoinverse
by Batson, Spielman, and Srivastava (2008).
  Furthermore we show how to compute all-pairs effective resistances from
$\widetilde{O}(n/\epsilon)$ size sketch in $\widetilde{O}(n^2/\epsilon)$ time.
This improves upon the previous best running time of
$\widetilde{O}(n^2/\epsilon^2)$ by Spielman and Srivastava (2008).
