Back to search

Georgia Institute of Technology

Analysis and Maintenance of Graph Laplacians via Random Walks

Abstract

dc:description.abstract

Graph Laplacians arise in many natural and artificial contexts. They are linear systems associated with undirected graphs. They are equivalent to electric flows which is a fundamental physical concept by itself and is closely related to other physical models, e.g., the Abelian sandpile model. Many real-world problems can be modeled and solved via Laplacian linear systems, including semi-supervised learning, graph clustering, and graph embedding. More recently, better theoretical understandings of Laplacians led to dramatic improvements across graph algorithms. The applications include dynamic connectivity problem, graph sketching, and most recently combinatorial optimization. For example, a sequence of papers improved the runtime for maximum flow and minimum cost flow in many different settings. In this thesis, we present works that the analyze, maintain and utilize Laplacian linear systems in both static and dynamic settings by representing them as random walks. This combinatorial representation leads to better bounds for Abelian sandpile model on grids, the first data structures for dynamic vertex sparsifiers and dynamic Laplacian solvers, and network flows on planar as well as general graphs.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gao, Yu
Advisor dc:contributor.advisor
  • Peng, Richard
Committee members dc:contributor.committeemember
  • Baker, Matthew
  • Galil, Zvi
  • Singh, Mohit
  • Kelner, Jonathan A.

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/67186

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gao, Yu. Analysis and Maintenance of Graph Laplacians via Random Walks. Doctoral thesis, Georgia Institute of Technology, 2022. http://hdl.handle.net/1853/67186