CS Events

Qualifying Exam A Trio of Graph Problems
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Wednesday, December 13, 2023, 02:15pm - 03:30pm

Speaker: Vikrant Ashvinkumar

Location : CoRE 305

Committee: 

Professor Jie Gao

Professor Kostas Bekris

Assistant Professor Aaron Bernstein

Assistant Professor Karthik CS

Event Type: Qualifying Exam

Abstract: I will talk (in brief) about three graph problems, each considered in disparate models of computation.First, I will go over problems pertaining to structural balance in the streaming model. Here we consider complete graphs where each edge signals either a positive or negative relation. Such a graph is said to be balanced if there is no incentive to flip any of these relations. We give an $O(\log n)$ space algorithm for determining whether a graph is balanced, and a $\widetilde{O}(n)$ space algorithm which provides a certificate saying approximately how far away a graph is from being balanced. These results are complemented by various lower bounds.Then, I plan to talk about the classic problem of single source shortest paths (SSSP), but now in distributed and parallel models of computation. Most SSSP algorithms in these models do not work when there are negative weight edges present. We show how any such algorithm which pays $T$ can be used in a blackbox fashion to construct an almost as good SSSP algorithm which pays $Tn^{o(1)}$, but which now works when there are negative weight edges.Finally, I want to discuss the problem of sending probes from a selection of $k$ vantage points to every other vertex in a graph, with the aim of maximizing the number of bottleneck edges discovered by these probes. We give an efficient polytime $(1-1/e)$ approximation algorithm in the non-adaptive setting, along with results (and tentative approaches) when we seek instance-optimality and/or are afforded adaptivity.List of Papers:Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance (https://arxiv.org/pdf/2306.00668.pdf)Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights (https://arxiv.org/pdf/2303.00811.pdf)Vantage Point Selection Algorithms for Bottleneck Capacity Estimation (not available yet)

: 

Contact  Professor Jie Gao