Interactive process analysis for graphs and distributed systems

Abstract

In this thesis, we study several interactive processes on graphs and distributed systems. We explore theoretical analyses for previous problems on them and propose enhanced solutions.

First, we consider a generalized diffusion process on hypergraphs to define a Laplacian operator recovering important spectral properties. Recent work [Louis STOC 2015, Chan et al. JACM 2018] only focused on a diffusion process in which each hyperedge directs flow only from vertices with the maximum density to those with the minimum density, while ignoring vertices having strict in-between densities. In our generalized diffusion process, vertices in a hyperedge can act as mediators to receive flow from vertices with maximum density and deliver flow to those with minimum density. Our analysis shows that there is a family of operators whose spectral properties are related to hypergraph conductance, and provides a powerful tool to enhance the development of spectral hypergraph theory. Moreover, since every vertex can participate in the new diffusion model at every instant, this can potentially have wider practical applications.

Next, we revisit the opinion susceptibility problem in [Abebe et al. KDD 2018], in which agents influence one another's opinions through an iterative process. Each agent has some fixed innate opinion. In each step, the opinion of an agent is updated to some convex combination between its innate opinion and the weighted average of its neighbors' opinions in the previous step. The resistance of an agent measures the importance it places on its innate opinion in the above convex combination. Under non-trivial conditions, this iterative process converges to some equilibrium opinion vector. For the unbudgeted variant of the problem, the goal is to select the resistance of each agent (from some given range) such that the sum of the equilibrium opinions is minimized. We analyze the structure of the objective function, and show that any local optimum is also a global optimum, even though the objective might not be convex. Furthermore, we combine the iterative process and the local search paradigm to design efficient algorithms that can solve the unbudgeted variant of the problem optimally on large-scale graphs containing millions of nodes.

Finally, we consider low-memory robust simulation of more general client-server interactive protocols over noisy channels, in which a leader communicates with other members/servers, who do not communicate among themselves. Previous work [Haeupler FOCS 2014] studied robust simulation of two-party interactive protocols over oblivious, as well as adaptive, noisy channels, which can circumvent the theoretical communication rate lower bound. However, a drawback of his work is that each party needs to remember the whole history of the simulated transcript. We resolve this issue by saving hashes of prefixes of past transcripts. In the two-party setting, our simulation has the same dependence on the error rate as in [Haeupler FOCS 2014], and in the client-server setting it also depends on the number of servers. Furthermore, since our approach does not remember the complete transcript history, our current technique can defend only against oblivious corruptions.