Event Details

I will present a new algorithm, called FastMap, for embedding the vertices of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two vertices in this space approximates the length of the shortest path between them in the given graph. FastMap’s novelty is that it preserves a quadratic number of pairwise distances between all the vertices but does not invest quadratic time for doing so. Instead, it runs in time near-linear in the size of the graph. FastMap’s efficiency leads to many applications, including but not limited to: (a) speeding up shortest-path computations in goal-directed A* search, (b) solving useful graph-theoretic combinatorial problems using geometric interpretations, (c) efficiently computing measures of centrality on large graphs, (d) embedding directed graphs in potential fields, (e) new algorithms for community detection and block modeling, and (f) new ways of doing machine learning on graphs.

TALK NOT RECORDED

Speaker Bio

Prof. Satish Kumar Thittamaranahalli (T. K. Satish Kumar) leads the Collaboratory for Algorithmic Techniques and Artificial Intelligence at the Information Sciences Institute of the University of Southern California. He is a faculty member in USC’s Department of Computer Science, Department of Physics and Astronomy, and Department of Industrial and Systems Engineering. He has published extensively on numerous topics spanning such diverse areas as Constraint Reasoning, Planning and Scheduling, Probabilistic Reasoning, Machine Learning and Data Informatics, Robotics, Combinatorial Optimization, Approximation and Randomization, Heuristic Search, Model-Based Reasoning, Computational Physics, Knowledge Representation, and Spatio-Temporal Reasoning. He has served on the Program Committees of many international conferences and is a winner of four Best Paper Awards.

Prof. Kumar received his PhD in Computer Science from Stanford University in March 2005. In the past, he has also been a Visiting Student at the NASA Ames Research Center, a Postdoctoral Research Scholar at the University of California, Berkeley, a Research Scientist at the Institute for Human and Machine Cognition, a Visiting Assistant Professor at the University of West Florida, and a Senior Research and Development Scientist at Mission Critical Technologies.