BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69d0d7025881b
DTSTART;TZID=America/Toronto:20240726T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240726T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-carla-groenland
SUMMARY:Tutte Colloquium - Carla Groenland
CLASS:PUBLIC
DESCRIPTION:TITLE: Tight bounds for reconstructing graphs from distance qu
 eries\n\nSPEAKER:\n Carla Groenland\n\nAFFILIATION:\n TU Delft\n\nLOCATION
 :\n MC 5501\n\nABSTRACT: Suppose you are given the vertex set of a graph 
 and you\nwant to discover the edge set. An oracle can tell you\, given two
 \nvertices\, what the distance is between these vertices in the graph.\n(F
 or example\, in a computer network\, this would represent the minimum\nnum
 ber of communication links needed to send a message from one\ncomputer to 
 another.) Based on the answer\, you may select the next\nquery. The (label
 led) graph is reconstructed when there is a single\nedge set compatible wi
 th the answers. How many queries are needed\, in\nthe worst case? The ques
 tion becomes interesting for bounded degree\ngraphs. We provide tight boun
 ds for various classes of graphs\,\nimproving both the lower and upper bou
 nd\, in both the randomized and\ndeterministic setting. 
DTSTAMP:20260404T091650Z
END:VEVENT
END:VCALENDAR