On November 29, Ph.D. candidate Olivia Simpson faced her advisor and other members of her dissertation committee for the final defense of her doctorate in Computer Science. She debriefed the committee and took questions on the subject of her dissertation: "Local and Distributed Computation for Large Graphs."
"Graphs are a powerful and expressive means for storing and working with data," according Simpson's dissertation abstract. "As the demand for fast data analysis increases, data is simultaneously becoming intractably large. To address these space constraints, there is a need for graph algorithms which do not require access to the full graph."
In her thesis, Simpson explored graph algorithms in a variety of computational settings, including local computation that uses the output of small, local queries. In the context of distributed computation, the local methods were extended "where a graph is stored across processors that can communicate via communication links in a number of rounds." The third setting is dynamic, one in which the graph changes over time.
A key tool for computation in each of these settings is random walks, and in her talk, Simpson offered a quantitative analysis of random walks for local computations on a static, centralized graph. She also introduced a random-walk simulation method for computing a vertex ranking known as the heat kernel pagerank of the graph. "We then show how to adapt this method to both the distributed and dynamic setting," noted Simpson. "With an efficient algorithm for simulating random walks in each of these computational settings, we design fast graph algorithms for modern, flexible computational paradigms."
The committee signed off on Simpson's defense of her dissertation, and pending filing graduation paperwork this Friday, she becomes CSE's newest Ph.D. alum. She leaves big shoes to fill. Simpson was president of Graduate Women in Computing (GradWIC) two years in a row ending in June 2015, and subsequently treasurer of the group. Also in 2015, she was awarded the CSE graduate award for contributions to diversity, and in 2012 Simpson received the inaugural Yahoo! Yodel Your Thoughts Award for an essay on the importance of strong female role models in science and engineering fields.