BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20171029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20180325T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.13051.field_data.0@www.open.diag.uniroma1.it
DTSTAMP:20260409T070826Z
CREATED:20180319T212358Z
DESCRIPTION:We prove information theoretic lower bounds for the space compl
 exity of fault-tolerant c-approximate diameter and radius data structures 
 (oracles). Our bounds for the diameter oracle are tight for any approximat
 ion factor c < 3/2\, and in the single-failure model our bounds are also t
 ight for any c >= 2. For c = 3/2\, we show a single-failure fault-tolerant
  oracle that uses significantly less space than the tight lower bound of t
 he c < 3/2 case. For the radius oracle our bounds are tight for any approx
 imation factor in the single-failure model.Our results almost completely s
 ettle the space complexity of fault-tolerant approximate diameter and radi
 us oracles in the single-failure model\, leaving open only what happens in
  the diameter oracle when the approximation factor is 3/2 =< c < 2. Our re
 sults also imply strong space complexity separation between the diameter a
 nd radius oracles.Joint work with Sarel Cohen.
DTSTART;TZID=Europe/Paris:20180322T120000
DTEND;TZID=Europe/Paris:20180322T120000
LAST-MODIFIED:20191008T082902Z
LOCATION:Aula B203 - DIAG - Via Ariosto 25
SUMMARY:Tight Space Lower Bounds for Fault-Tolerant Approximate Diameter an
 d Radius - Omer Gold (Tel-Aviv University)
URL;TYPE=URI:http://www.open.diag.uniroma1.it/node/13051
END:VEVENT
END:VCALENDAR