Theory Lunch Seminar

  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University

Spanners and Sparsifiers for Graphs on Euclidean Point Sets

Consider a graph G obtained from Euclidean point sets by taking the Euclidean distance between points, raised to some power p. In this talk, we show how to construct spanners of such a graph efficiently in low dimension, and show how to find linear size sparsifiers in nearly linear time in the high dimensional setting. The family of graphs G has been considered before for alternate problems, including minimum cost matching, MSTs, and more.

Theory Youtube Channel

For More Information, Please Contact: