4 papers
One-way Communication Complexity of Minimum Vertex Cover in General Graphs
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman
We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the \(k\)-party one-way communication model. Edges of an arbitrary \(n\)-ve…
Fully Dynamic (Î+1) Coloring Against Adaptive Adversaries
Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include vertex coloring, maximal…
Sample Complexity of Linear Regression Models for Opinion Formation in Networks
Haolin Liu, Rajmohan Rajaraman, Ravi Sundaram +3
Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal…
Online Paging with Heterogeneous Cache Slots
Marek Chrobak, Samuel Haney, Mehraneh Liaee +4
It is natural to generalize the online -Server problem by allowing each request to specify not only a point , but also a subset of servers that may serve it. For uniform…