BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1518
DTSTAMP:20250227T043503Z
SUMMARY:Improved Distance (Sensitivity) Oracles with Subquadratic Space
DESCRIPTION:Speaker: Keerti Choudhary (IIT Delhi)\n\nAbstract: \nA distance
  oracle for a graph $G = (V\, E)$ is a data structure that enables fast re
 trieval of approximate distances between any pair of query vertices. The o
 racle has a stretch of $(\\alpha\, \\beta)$ if the estimated distance $\\h
 at{d}(x\, y)$ for any $x\,y\\in V$ satisfies the inequality:$$d(x\, y) \\l
 eq \\hat{d}(x\, y) \\leq \\alpha \\cdot d(x\, y) + \\beta\, ~ \\forall x\,
  y \\in V.$$In the fault-tolerant model\, a related well-studied problem i
 s the distance sensitivity oracle (DSO). Here\, given a query vertex pair 
 $(s\, t)$ and a set $F$ of failed edges\, the goal is to efficiently appro
 ximate the distance between $s$ and $t$ in the graph $G - F$. Over the pas
 t two decades\, significant efforts have been made to design compact dista
 nce oracles for both static and fault-prone graphs.In this talk\, I will d
 iscuss the following results:1. The first static distance oracle with subq
 uadratic space and sublinear query time that achieves a stretch of $(1 + \
 \epsilon\, O(1))$\, where $\\epsilon > 0$ is a small constant.2. The first
  $f$-fault-tolerant DSO with subquadratic space and constant stretch\, ind
 ependent of $f$.\nShort Bio:\nKeerti Choudhary is an Assistant Professor i
 n the Department of Computer Science and Engineering at IIT Delhi. Prior t
 o this\, she held post-doctoral positions at Tel Aviv University and the W
 eizmann Institute of Science. She earned her Ph.D. in Computer Science and
  an Integrated M.Sc. in Mathematics from IIT Kanpur. Her research interest
 s lie in graph theory\, fault-tolerant structures\, and dynamic graph algo
 rithms.\n
URL:https://www.tcs.tifr.res.in/web/events/1518
DTSTART;TZID=Asia/Kolkata:20250227T160000
DTEND;TZID=Asia/Kolkata:20250227T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR