Seminar Details

Navigability captures the ability of a complex network to support efficient, decentralized search. The concept has a rich history, from Milgram’s "six degrees of separation" to Kleinberg’s computational model of small-world phenomena. Over the past decade, navigable graphs have also emerged as an important principle behind state-of-the-art heuristics for nearest neighbor search. In this talk, I will present a perspective on this development through the lens of approximation algorithms: given a dataset and a distance function, how efficiently can we construct the (approximately) sparsest navigable graph?

Based on joint work with Sanjeev Khanna and Erik Waingarten.