Gary Miller Professor Emeritus Website Email gm2f@andrew.cmu.edu Phone (412) 268-2631 Department Computer Science Department Research Interests Theory Algorithms and Complexity Research/Teaching Statement My main interest is in sequential and parallel algorithm design. Of particular interest are problems that arise in scientific computation and image processing. We have been working on three classes of problems. Our work is both more theoretical yet more practical since we require two important properties of our algorithms: they should be both be fast and have strong guarantees of quality, size, and speed. Mesh Generation The question of correctly and efficiently partitioning space into tetrahedra with good aspect ratio so that the features appear in the mesh is at least a fifty year old problem. The computer science community has been working on this problem for about twenty years. The most accurate simulations in the science, engineering, and graphic require small size quality meshes. CMU has been a leader on this problem for the last fifteen years. Spectral Graph Theory The interplay between graph theory and linear algebra is possibly one of the most interesting and practical areas in modern algorithm design. Possibly the most famous example is Google PAGE-RANK which is the Perron-Frobenius eigenvector of the link graph. The second example is the interplay between fast linear solvers and graph theory. We have ongoing collaboration on fast solvers and eigen calculations. These new algorithm work in near linear time. Image Processing We are interested in fast and reliable algorithm for image processing. Of special interest is 3D medical image processing. Our main tool that allows us to get new fast algorithms is spectral graph theory. This has allowed us to compute eigenvectors of our image as speed comparable to many simple filtering algorithms. We are also using interior point methods from convex optimization to de-noise images. Again these methods all use our fast solvers for speed. Publications Conference Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph 2020 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 2020-January:411-425 Chu T, Miller GL, Sheehy DR Conference Hardy-muckenhoupt bounds for Laplacian eigenvalues 2019 • Leibniz International Proceedings in Informatics • 145: Miller GL, Walkington NJ, Wang AL Conference Simple and Scalable Constrained Clustering: A Generalized Spectral Method 2016 • JMLR workshop and conference proceedings • 51:445-454 Cucuringu M, Koutis I, Chawla S, Miller G, Peng R Conference Approximate Center Points with Proofs 2009 • Proceedings of the Annual Symposium on Computational Geometry • 153-158 Miller GL, Sheehy DR Conference Combinatorial Preconditioners and Multilevel Solvers for Problems in Computer Vision and Image Processing 2009 • Lecture Notes in Computer Science • 5875:1067-1078 Koutis I, Miller GL, Tolliver D
Conference Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph 2020 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 2020-January:411-425 Chu T, Miller GL, Sheehy DR
Conference Hardy-muckenhoupt bounds for Laplacian eigenvalues 2019 • Leibniz International Proceedings in Informatics • 145: Miller GL, Walkington NJ, Wang AL
Conference Simple and Scalable Constrained Clustering: A Generalized Spectral Method 2016 • JMLR workshop and conference proceedings • 51:445-454 Cucuringu M, Koutis I, Chawla S, Miller G, Peng R
Conference Approximate Center Points with Proofs 2009 • Proceedings of the Annual Symposium on Computational Geometry • 153-158 Miller GL, Sheehy DR
Conference Combinatorial Preconditioners and Multilevel Solvers for Problems in Computer Vision and Image Processing 2009 • Lecture Notes in Computer Science • 5875:1067-1078 Koutis I, Miller GL, Tolliver D
