BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1560
DTSTAMP:20250701T052748Z
SUMMARY:Approximating Dasgupta Cost of Clusterable Graphs in Sublinear Time
DESCRIPTION:Speaker: Akash Kumar (IIT Bombay)\n\nAbstract: \nIn a 2002 work
 \, Goldreich and Ron gave sublinear time algorithms for testing graph expa
 nsion. In 2015\, Czumaj\, Peng\, and Sohler extended these ideas to test 
 -clusterability in roughly  time. However\, no sublinear time algorithms
  are known that give any information about the cluster structure of a -cl
 usterable graph. That is\, no such algorithms are known for understanding 
 how clusters connect to each other. As a simple example\, one may wonder 
 whether it is possible to locally distinguish between the "cluster graph" 
 forming a line from a cluster graph which forms a clique.\nIn this talk\, 
 I will present sublinear time algorithms for estimating the hierarchical c
 luster structure of -clusterable graphs. The measure we use is Dasgupta c
 ost\, which is a standard way to evaluate hierarchical clustering. Our mai
 n result is a sublinear time algorithm that approximates the Dasgupta cost
  of a -clusterable graph using a small number of randomly chosen seed ver
 tices with known cluster labels.\nIn particular\, I will describe an algor
 ithm that gives an  approximation to the Dasgupta cost of  in roughly
   time\, using about  seeds. This can be viewed as a sublinear time si
 mulation of the algorithm of Charikar and Chatziafratis (SODA 2017) on clu
 sterable graphs.\nThis is joint work with Michael Kapralov\, Silvio Lattan
 zi\, Aida Mousavifar\, and Weronika Kaminska.\nShort Bio:Akash Kumar is a 
 James R. Isaac Chair Assistant Professor in the Department of Computer Sci
 ence and Engineering at IIT Bombay\, where he has been on the faculty sinc
 e December 2022. His research interests are in spectral graph theory and p
 roperty testing. He is also one of the co-editors of the Property Testing 
 Blog\, where besides sublinear algorithms\, he enjoys writing about recent
  developments in topics such as Boolean functions and Markov chains.\n
URL:https://www.tcs.tifr.res.in/web/events/1560
DTSTART;TZID=Asia/Kolkata:20250708T160000
DTEND;TZID=Asia/Kolkata:20250708T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR