Please note: This PhD seminar will take place in DC 1304 and online.
Robert Wang, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Lap Chi Lau
In the load-balancing problem, we have an n-vertex bipartite graph G=(L,R,E) between a set of clients and servers. The goal is to find an assignment of all clients to the servers, while minimizing the maximum load on each server, where load of a server is the number of clients assigned to it. We study load-balancing in the one-way communication model: the edges of the input graph are partitioned between Alice and Bob, and Alice needs to send a message to Bob for him to output the solution.
We show that settling the one-way communication complexity of load-balancing is equivalent to a natural sparsification problem for load-balancing. We then prove a dual interpretation of this sparsifier, showing that the minimum density of a sparsifier is effectively the same as the maximum density one can achieve for an extremal graph family that is new to this paper, called Matching-Contractors; these graphs are intimately connected to the well-known Ruzsa-Szemeredi graphs and generalize them in certain aspects. Our chain of equivalences thus shows that the one-way communication complexity of load-balancing can be reduced to a purely graph theoretic question: what is the maximum density of a Matching-Contractor on n vertices? Finally, we present a novel combinatorial construction of some-what dense Matching-Contractors, which implies a strong one-way communication lower bound for load-balancing: any one-way protocol (even randomized) with O~(n) communication cannot achieve a better than n^{1/4−o(1)}-approximation. Previously, no non-trivial lower bounds were known for protocols with even O(nlogn) bits of communication. Our result also implies the first non-trivial lower bounds for semi-streaming load-balancing in the edge-arrival model, ruling out n^{1/4−o(1)}-approximation in a single-pass.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.