In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy
Nguyen Dinh Pham
will defend his dissertation
Probabilistic Models and Algorithmic Analysis of Network Problems
AbstractNetwork-related problems span over many areas in computer science. In this dissertation, we investigate two problems-- one is in the domain of distributed computing, and the other is in the domain of graph mining. We approach these problems by the probabilistic tools, to model, analyze, and design algorithms. In the first problem, we aim to improve upon the known bounds of some fundamental distributed algorithms, Minimum Spanning Tree (MST) in particular. We propose the smoothing model, where the key is to randomly and slightly alter the input, and show new asymptotic bounds. For the MST problem, we also design an algorithm that almost matches the lower bound. In the second problem, we study influence spreading in networks, which is a stochastic process. We propose a new optimization problem: minimizing the seed set with probabilistic guarantee on the influence. This problem relates non-submodular target function, and is hard even for an approximation solution. We design an efficient algorithm using relaxed multi-criterial approximation and Monte Carlo sampling, with theoretically proven properties, and supportive empirical results.
Date: Tuesday, November 12, 2019
Time: 1:00 - 3:00 PM
Place: PGH 550
Advisor: Dr. Gopal Pandurangan
Faculty, students, and the general public are invited.