Computer Science Thesis Oral

Monday, May 2, 2016 - 12:45pm


McWilliams Classroom 4303 Gates & Hillman Centers



Convex optimization is one of the most robust tools for automated data analysis. It has widespread applications in fields such as machine learning, computer vision, combinatorial optimization and scientific computing. However, the rapidly increasing volume and complexity of data that needs to be processed often renders general-purpose algorithms unusable. This thesis aims to address this issue through development of very fast algorithms for core convex optimization problems, with a focus on graphs. To this end, we: Develop nearly optimal algorithms for the Fermat-Weber (geometric median) problem, a fundamental task in robust estimation and clustering. Investigate how to approximate massive amounts of high-dimensional data in a restrictive streaming setting, achieving optimal tradeoffs. Develop the fastest algorithm for solving linear systems on undirected graphs.   This is achieved through improved clustering algorithms and better understanding of the interplay between combinatorial and numerical aspects of previous approaches. Show the existence of clustering and oblivious routing algorithms for a broad family of directed graphs, in hopes of advancing the search for faster maximum flow algorithms. The unifying theme of these results is careful analysis of optimization algorithms in high-dimensional spaces, and mixing combinatorial and numerical approaches. Thesis Committee: Gary L. Miller (Chair) Anupam Gupta Daniel Sleator Shang-Hua Teng (University of Southern California)

For More Information, Contact:


Thesis Oral