[Theory] 2/26 Talks at TTIC: Nicole Wein, MIT

[Mary Marre]

*When:* Friday, February 26th at 11:10am CT

*Where:*   Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/j/92324413499?pwd=TU10blNuV09OZWw0UXdzQ3FwVU4yZz09>)*

*Who:* Nicole Wein, MIT


*Title: *Approximating the Diameter of a Graph

*Abstract:* I will talk about one of the central problems in fine-grained
complexity: computing the diameter of a graph (the largest distance between
two vertices). The best known algorithm for computing the diameter of a
graph is the naive algorithm of computing all-pairs shortest paths (APSP)
and taking the largest distance. Moreover, no significantly better
algorithm exists under the Strong Exponential Time Hypothesis. Running APSP
can be prohibitively slow for very large graphs, so we seek much faster
algorithms that produce an *approximation* of the diameter. I will talk
about algorithms and conditional lower bounds for approximating
the diameter of a graph. In particular, I will discuss the landscape of
time vs. accuracy trade-offs.

*Bio:* Nicole Wein is a final-year PhD student at MIT advised by Virginia
Vassilevska Williams. Her research interests are mainly in graph algorithms
including dynamic algorithms, parameterized algorithms, data structures,
and fine-grained complexity.

*Host:* Julia Chuzhoy <cjulia at ttic.edu>


Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210219/1f93d94e/attachment.html>