Fundamental limits of hypergraph edge partitioning

Hypergraph edge partitioning is a central problem in computer science, with broad impact in distributed computing and learning. It addresses the following question: given a sparse pattern of computations/interactions, how should these computations be distributed across machines while minimizing the amount of data/model state that must be replicated? In this setting, after given a collection of hyperedges (jobs) -- each consisting of up to d vertices from a ground set of size n (n files) -- one must assign these edges across N partitions (servers/shards) so as to minimize, for example, the vertex footprint, i.e., the maximum number of vertices that appear in any partition. This problem has attracted substantial attention, primarily from an algorithmic perspective, yet its fundamental performance limits remain largely unexplored. We here identify the fundamental limits of hypergraph edge partitioning -- optimized over all algorithms -- for a broad class of well-established probabilistic hypergraph models, and for hypergraphs that range from the fully dense, to the very sparse (with edge-set sizes down to linear in n). Rather surprisingly, optimality is achieved by a blind construction, whose vertex (file) placement is fixed a priori and is completely independent of the realized hypergraph (independent of the assigned tasks).