dc.contributor.author Vassilevska Williams, Virginia dc.date.accessioned 2018-05-24T18:10:43Z dc.date.available 2018-05-24T18:10:43Z dc.date.issued 2018-05-16 dc.identifier.uri http://hdl.handle.net/1853/59721 dc.description Presented as part of the Workshop on Algorithms and Randomness on May 16, 2018 at 10:15 a.m. in the Klaus Advanced Computing Building, Room 1116. en_US dc.description Virginia Vassilevska Williams is the Steven and Renee Finn Career Development Associate Professor at the Massachusetts Institute of Technology. Her research applies combinatorial and graph theoretic tools to various computational domains. My recent work has focused on the following domains: en_US 1) designing algorithms for shortest paths, pattern detection and other computational problems in graphs and matrices, 2) reducing fundamental computational problems to one another in a fine-grained way, sometimes showing equivalences, 3) studying how much graph distance information can be compressed, and 4) computational issues in social choice: when and how can one efficiently manipulate elections, tournaments and competitions, how to measure the quality of a voting rule, etc. dc.description Runtime: 45:57 minutes en_US dc.description.abstract Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be {\em approximated}. Chechik et al.\ [SODA 2014] showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $\tO(m^{3/2})$ time. Roditty and Vassilevska W.\ [STOC 13] showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-\eps})$ time algorithm for $\eps>0$ can achieve an approximation factor better than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than $3/2$. It was, however, completely plausible that a $3/2$-approximation is possible in linear time. en_US In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-\eps})$ time algorithm can achieve an approximation factor better than $5/3$. We provide similarly tight results for other distance-related parameters, also providing new algorithms. To establish the our lower bounds we study the $S$-$T$ Diameter problem: Given a graph and two subsets $S$ and $T$ of vertices, output the largest distance between a vertex in $S$ and a vertex in $T$. We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. In this talk I will explain the lower bound constructions for $S$-$T$ Diameter and will outline how one can extend them for Diameter as well. Joint work with Arturs Backurs, Nicole Wein, Liam Roditty and Gilad Segal. To appear in STOC 2018. dc.format.extent 45:57 minutes dc.language.iso en_US en_US dc.relation.ispartofseries Workshop on Algorithms and Randomness 2018 en_US dc.subject Algorithms en_US dc.subject Graph diameter en_US dc.subject Strong Exponential Time Hypothesis (SETH) en_US dc.title Towards Tight Approximation Bounds for Graph Diameter and Eccentricities en_US dc.type Lecture en_US dc.type Video en_US dc.contributor.corporatename Georgia Institute of Technology. Algorithms, Randomness and Complexity Center en_US dc.contributor.corporatename Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory en_US
﻿

### This item appears in the following Collection(s)

• ARC Talks and Events 
Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community