Timothy Chu
I'm a fifth year PhD student at Carnegie Mellon University in computer
science theory, who is very
fortunate to be advised by Gary Miller.
Dr. Miller is one of the rare advisors who meets students for
multiple hours a day. Working with him taught me the value of
pursuing unorthodox problems.
My research is in machine learning theory, spectral graph theory, and
computational geometry. My favorite work combines two or more of these
topics.
Selected Publications
- Metric Transforms and Low Rank Matrices, via Representation
Theory of the Real Hyperrectangle
Josh Alman, Timothy Chu, Gary Miller, Shyam Narayanan, Mark Sellke, Zhao
Song
Preprint [arXiv] .
This paper proves new results about kernel methods in
machine learning, metric transforms, and natural language processing. It does so
by introducing a new tool inspired by group symmetries, which we call
representation theory of the real hyperrectangle.
- Algorithms and Hardness for Linear Algebra on Geometric Graphs
Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
FOCS 2020 [arXiv].
This paper introduces spectral algorithms and hardness results on
geometric graphs, with applications to machine learning. One key result
is a significantly faster way to do spectral clustering in certain scenarios.
sparsifiers.
- Patching a hole in Spectral Clustering, via Cheeger/Buser
inequalities for probability densities.
Timothy Chu, Gary Miller, Noel
Walkington, Alex Wang
Preprint [arXiv].
This paper patches a longstanding issue in
spectral clustering, one of the most widely used clustering methods in
machine learning history.
Spectral clustering suffers from a core issue that it converges to a bad
partition of data when the data is drawn from certain well-behaved
probability densities.
This paper proposes new variants of spectral clustering that partition
probability densities nicely in both theory and practice.
Other Publications
- Exact Computation of a Manifold metric, via Lipschitz Embeddings
Timothy Chu, Gary Miller, Donald Sheehy
SODA 2020 [arXiv].
- Graph Sparsification, Spectral Sketches, and Faster Resistance
Computation, via Short Cycle Decomposition
Timothy Chu, Yu Gao, Richard Peng,
Sushant
Sachdeva, Saurabh
Sawlani, Junxing
Wang
FOCS 2018 [arXiv].
Invited to the SICOMP Special Issue.
- Constant Arboricity Spectral Sparsifiers
Timothy Chu, Michael Cohen, Jakub Pachocki, Richard Peng
Preprint [arXiv].
Teaching