T. Chu

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2020

Algorithms and Hardness for Linear Algebra on Geometric Graphs

Josh Alman, Timothy Chu, Aaron Schild +1

For a function $K : R^{d} \times R^{d} \to R_{\geq 0}$ , and a set $P = {x_{1}, \dots, x_{n}} \subset R^{d}$ of $n$ points, the $\mathsf{K…

cs.DS2018

Constant Arboricity Spectral Sparsifiers

Timothy Chu, Michael B. Cohen, Jakub W. Pachocki +1

We show that every graph is spectrally similar to the union of a constant number of forests. Moreover, we show that Spielman-Srivastava sparsifiers are the union of O(logn) forests…

cs.DS2018

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

Timothy Chu, Yu Gao, Richard Peng +3

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…