Show simple item record

dc.contributor.authorVassilevska Williams, Virginia
dc.descriptionPresented 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.descriptionVirginia 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: 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.en_US
dc.descriptionRuntime: 45:57 minutesen_US
dc.description.abstractAmong 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. 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.en_US
dc.format.extent45:57 minutes
dc.relation.ispartofseriesWorkshop on Algorithms and Randomness 2018en_US
dc.subjectGraph diameteren_US
dc.subjectStrong Exponential Time Hypothesis (SETH)en_US
dc.titleTowards Tight Approximation Bounds for Graph Diameter and Eccentricitiesen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameMassachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratoryen_US

Files in this item


This item appears in the following Collection(s)

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

Show simple item record