Seminars

View all Seminars  |  Download ICal for this event

Spectral Clustering Oracles in Sublinear Time

Series: Theory Seminar

Speaker: Dr. Michael Kapralov Assistant Professor School of Computer and Communication Sciences EPFL, Switzerland

Date/Time: Jul 23 16:00:00

Location: Microsoft teams - ONLINE

Abstract:
Given an n-vertex graph G that can be partitioned into a few clusters with good inner conductance and
ϵ-sparse boundary, i.e. admits a good clustering, can we quickly tell which cluster a given vertex belongs to? A clustering oracle is a small space data structure that provides query access to an approximate clustering of the input graph in sublinear time. In this talk I will describe a clustering oracle that provides query access to an
O(ϵlogk) -approximate clustering in time about n1/2+O(ϵ), where k is the number of clusters, which is essentially optimal for constant k. Our main tool is a new way of obtaining dot product access to the spectral embedding of a clusterable graph in sublinear time using the distribution of a few short random walks started at uniformly random vertices in the graph.

Microsoft teams link:

Link

Host Faculty: Dr. Anand Louis