BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//128.220.13.64//NONSGML kigkonsult.se iCalcreator 2.20//
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Johns Hopkins Algorithms and Complexity
X-WR-CALDESC:
X-FROM-URL:https://www.cs.jhu.edu/~mdinitz/theory
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:STANDARD
DTSTART:20221106T020000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20230312T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ai1ec-349@www.cs.jhu.edu/~mdinitz/theory
DTSTAMP:20221126T124551Z
CATEGORIES:
CONTACT:
DESCRIPTION:Speaker: Hung Le\nAffiliation: University of Massachusetts\, Am
herst\nTitle: Reliable Spanners: Locality-Sensitive Orderings Strike Back
\nAbstract:\nA highly desirable property of networks is robustness to fail
ures.\nConsider a metric space $(X\,d_X)$\, a graph $H$ over $X$ is a $\\v
artheta$-reliable $t$-spanner if\, for every set of failed vertices $B\\su
bset X$\, there is a superset $B^+\\supseteq B$ such that the induced subg
raph $H[X\\setminus B]$ preserves all the distances between points in $X\\
setminus B^+$ up to a stretch factor $t$\, while the expected size of $B^+
$ is as most $(1+\\vartheta)|B|$. Such a spanner could withstand a catastr
ophe: failure of even $90\\%$ of the network.\nBuchin\, Har-Peled\, and Ol
ah showed how to construct a sparse reliable spanner for Euclidean space f
rom Euclidean locality-sensitive orderings\, an object introduced by Chan\
, Har-Peled\, and Jones. In this talk\, we extend their approach to non-Eu
clidean metric spaces by generalizing the ordering of Chan\, Har-Peled\, a
nd Jones to doubling metrics and introducing new types of locality-sensiti
ve orderings for other metric spaces. We also show how to construct reliab
le spanners from the newly introduced locality-sensitive orderings via rel
iable 2-hop spanners for paths. The highlight of our results is that the n
umber of edges in our spanner has no dependency on the spread.
DTSTART;TZID=America/New_York:20210303T120000
DTEND;TZID=America/New_York:20210303T130000
LOCATION:https://wse.zoom.us/j/91450299380
SEQUENCE:0
SUMMARY:[Theory Seminar] Hung Le
URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-hung-le/
X-COST-TYPE:free
X-ALT-DESC;FMTTYPE=text/html:\\n\\n\\n\\n\\nSpeaker: Hung
Le

\nAffiliation: University of Massachusetts\, Amherst

\nTitl
e: Reliable Spanners: Locality-Sensitive Orderings Strike Back

\nAb
stract:

\nA highly desirable property of networks is robustness to fa
ilures.

\nConsider a metric space $(X\,d_X)$\, a graph $H$ over $X$ i
s a $\\vartheta$-reliable $t$-spanner if\, for every set of failed vertice
s $B\\subset X$\, there is a superset $B^+\\supseteq B$ such that the indu
ced subgraph $H[X\\setminus B]$ preserves all the distances between points
in $X\\setminus B^+$ up to a stretch factor $t$\, while the expected size
of $B^+$ is as most $(1+\\vartheta)|B|$. Such a spanner could withstand a
catastrophe: failure of even $90\\%$ of the network.

\nBuchin\, Har
-Peled\, and Olah showed how to construct a sparse reliable spanner for Eu
clidean space from Euclidean locality-sensitive orderings\, an object intr
oduced by Chan\, Har-Peled\, and Jones. In this talk\, we extend their app
roach to non-Euclidean metric spaces by generalizing the ordering of Chan\
, Har-Peled\, and Jones to doubling metrics and introducing new types of l
ocality-sensitive orderings for other metric spaces. We also show how to c
onstruct reliable spanners from the newly introduced locality-sensitive or
derings via reliable 2-hop spanners for paths. The highlight of our result
s is that the number of edges in our spanner has no dependency on the spre
ad.

\n
END:VEVENT
END:VCALENDAR