Aaron Bernstein, New York University (NYU)

Abstract

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. Motivated by understanding the streaming complexity of this problem, we study load-balancing in the one-way (two-party) communication model:

the edges of the input graph are partitioned between Alice and Bob, and Alice needs to send a short message to Bob for him to output a solution of the entire graph.

We show that settling the one-way communication complexity is equivalent to a problem in extremal combinatorics. We define a new kind of graph called a matching contractor, which can be thought of as a generalization of the well-known Ruzsa-Szemeredi graphs. We then show that the one-way communication complexity of load-balancing can be reduced to the question: what is the maximum density of a rsplus on $n$ vertices?

As our final result, 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(npolylog) communication cannot achieve a better than $n^{frac14-o(1)}$-approximation. Previously, no non-trivial lower bounds were known for protocols with even $O(nlog{n})$ bits of communication (a better-than 2-approximation lower bound is trivial). Our result also implies the first non-trivial lower bounds for semi-streaming algorithms for load-balancing, ruling out $n^{frac14-o(1)}$-approximation in a single-pass. 

Based on joint work with Sepehr Assadi, Lap Chi Lau, Zachary Langley, and Robert Wang (SODA 2025).

See: https://theory.cs.rutgers.edu/theory_seminar