[Theory] REMINDER: 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>*


On Thu, Feb 25, 2021 at 3:30 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Fri, Feb 19, 2021 at 6:04 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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/20210226/4205b48e/attachment.html>