BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20251026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260424T040551Z
UID:6904a1211bd03622259774@ist.ac.at
DTSTART:20251113T110000
DTEND:20251113T120000
DESCRIPTION:Speaker: Da Wei Zheng\nhosted by TCS Seminar\nAbstract: Abstrac
 t:A simple algorithm for computing the diameter of an unweighted n-vertex 
 graph is to run a breadth-first search from every vertex of the graph. Thi
 s leads to quadratic time algorithms for computing diameter in sparse grap
 hs and geometric intersection graphs. There are matching fine-grained lowe
 r bounds that show that this is essentially optimal in general sparse grap
 hs and many types of geometric intersection graphs\; it is not possible to
  get a truly subquadratic time algorithm for diameter computation.To contr
 ast\, we give the first truly subquadratic time algorithm\, with $O^*(n^{2
 -1/18})$ running time\, for computing the diameter of an $n$-vertex unit-d
 isk graph. Our result is obtained as an instance of a general framework\, 
 applicable to different graph families and distance problems. Surprisingly
 \, our framework completely bypasses sublinear separators (or -divisions) 
 which were used in all previous subquadratic time algorithms for diameter.
  Instead\, we use low-diameter decompositions in their most elementary for
 m. To obtain these results\, we exploit bounded VC-dimension of set system
 s associated with the input graph\, as well as new ideas with geometric da
 ta structures.Based on joint work to appear in FOCS 2025 with Timothy M. C
 han\, Hsien-Chih Chang\, Jie Gao\, Sndor Kisfaludi-Bak\, and Hung Le. Arxi
 v: https://arxiv.org/abs/2510.16346
LOCATION:Office Bldg West / Ground floor / Foyer seminar room (I21.EG.128)\
 , ISTA
ORGANIZER:achaturv@ist.ac.at
SUMMARY:Da Wei Zheng: Truly Subquadratic Time Algorithms for Diameter in Ge
 ometric Intersection Graphs and Beyond
URL:https://talks-calendar.ista.ac.at/events/6130
END:VEVENT
END:VCALENDAR