BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20210723T120000Z
UID:799e0e38ff004729ad3cca329ecae140-174
DTSTAMP:19700101T120016Z
DESCRIPTION:Spectral Clustering Oracles in Sublinear Time
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/174/spectral-clustering-oracles-in-sublinear-time/
SUMMARY: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:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
DTSTART:20210723T120000Z
END:VEVENT
END:VCALENDAR