BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Halıcıoğlu Data Science Institute - UC San Diego - ECPv6.16.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Halıcıoğlu Data Science Institute - UC San Diego
X-ORIGINAL-URL:https://datascience.ucsd.edu
X-WR-CALDESC:Events for Halıcıoğlu Data Science Institute - UC San Diego
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20220313T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20221106T090000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20230312T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20231105T090000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20240310T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20241103T090000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Los_Angeles:20230329T140000
DTEND;TZID=America/Los_Angeles:20230329T153000
DTSTAMP:20260718T223726
CREATED:20230302T000631Z
LAST-MODIFIED:20230323T175902Z
UID:10000353-1680098400-1680103800@datascience.ucsd.edu
SUMMARY:Distance-Estimation in Modern Graphs: Algorithms and Impossibility | Nicole Wein
DESCRIPTION:The size and complexity of today’s graphs present challenges that necessitate the discovery of new algorithms. One central area of research in this endeavor is computing and estimating distances in graphs. In this talk I will discuss two fundamental families of distance problems in the context of modern graphs: Diameter/Radius/Eccentricities and Hopsets/Shortcut Sets. The best-known algorithm for computing the diameter (largest distance) of a graph is the naive algorithm of computing all-pairs shortest paths and returning the largest distance. Unfortunately\, this can be prohibitively slow for massive graphs. Thus\, it is important to understand how fast and how accurately the diameter of a graph can be approximated. I will present tight bounds for this problem via conditional lower bounds from fine-grained complexity. Secondly\, for a number of settings relevant to modern graphs (e.g. parallel algorithms\, streaming algorithms\, dynamic algorithms)\, distance computation is more efficient when the input graph has low hop-diameter. Thus\, a useful preprocessing step is to add a set of edges (a hopset) to the graph that reduces the hop-diameter of the graph\, while preserving important distance information. I will present progress on upper and lower bounds for hopsets. \n  \nBio: Nicole Wein is a Simons Postdoctoral Leader at DIMACS at Rutgers University. Previously\, she obtained her Ph.D. from MIT advised by Virginia Vassilevska Williams. She is a theoretical computer scientist and her research interests include graph algorithms and lower bounds including in the areas of distance-estimation algorithms\, dynamic algorithms\, and fine-grained complexity.
URL:https://datascience.ucsd.edu/event/nicole-wein/
LOCATION:SDSC\, The Auditorium\, 9836 Hopkins Dr\, La Jolla\, San Diego\, CA\, United States
CATEGORIES:Seminar
END:VEVENT
END:VCALENDAR