BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Merav Parter (Weizmann Institute of Science)
DTSTART:20220223T180000Z
DTEND:20220223T190000Z
DTSTAMP:20260423T021005Z
UID:TCSPlus/35
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/35/"
 >New Diameter Reducing Shortcuts: Breaking the $O(\\sqrt{n})$ Barrier</a>\
 nby Merav Parter (Weizmann Institute of Science) as part of TCS+\n\n\nAbst
 ract\nFor an $n$-vertex digraph $G=(V\,E)$\, a \\emph{shortcut set} is a (
 small) subset of edges $H$ taken from the transitive closure of $G$ that\,
  when added to $G$ guarantees that the diameter of $G \\cup H$ is small. S
 hortcut sets\, introduced by Thorup in 1993\, have a wide range of applica
 tions in algorithm design\, especially in the context of parallel\, distri
 buted and dynamic computation on directed graphs. A folklore result in thi
 s context shows that every $n$-vertex digraph admits a shortcut set of lin
 ear size (i.e.\, of $O(n)$ edges) that reduces the diameter to $\\widetild
 e{O}(\\sqrt{n})$. Despite extensive research over the years\, the question
  of whether one can reduce the diameter to $o(\\sqrt{n})$ with $\\widetild
 e{O}(n)$ shortcut edges has been left open.\n\nIn this talk\, I will prese
 nt the first improved diameter-sparsity tradeoff for this problem\, breaki
 ng the $\\sqrt{n}$ diameter barrier. Specifically\, we show an $O(n^{\\ome
 ga})$-time randomized algorithm for computing a linear shortcut set that r
 educes the diameter of the digraph to $\\widetilde{O}(n^{1/3})$. We also e
 xtend our algorithms to provide improved $(\\beta\,\\epsilon)$ hopsets for
  $n$-vertex weighted directed graphs.\n\nJoint work with Shimon Kogan.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/35/
END:VEVENT
END:VCALENDAR