color:#002060;mso-ansi-language:EN-US">
color:#002060;mso-ansi-language:EN-US">The efficient allocation of data, tasks, and communication resources is a fundamental challenge in distributed computing systems, especially when large-scale functions decompose into subfunctions with multi-way dependencies among input files. Such dependencies arise naturally in distributed learning, coded computing, analytics, scientific computing, similarity search, covariance estimation, and higher-order statistical computation. This thesis develops a unified combinatorial framework for these settings by modeling files as vertices, subfunctions as hyperedges, and task allocation as hypergraph edge partitioning.
color:#002060;mso-ansi-language:EN-US">In the model, a master node coordinates (N) workers to compute a function over a library of (n) files. Each subfunction depends on a subset of (d) files, and the subfunction set is represented by a hyperedge set (mathbf X). The objective is to partition (mathbf X) across workers while minimizing the maximum number of distinct files communicated to any worker, denoted by (pi_{mathbf X}), and keeping the computational load balanced, as measured by (delta_{mathbf X}). This formulation captures the communication--computation tradeoff and motivates deterministic allocation schemes with guarantees
color:#002060;mso-ansi-language:EN-US">The thesis first connects this allocation problem to classical combinatorial design theory. Steiner systems provide a natural benchmark, since they can yield perfectly balanced task allocation with minimal file replication when the required parameters exist. However, their restrictive divisibility and existence conditions make them unsuitable as a universal design tool. To overcome this limitation, the thesis develops the Interweaved-Cliques (IC) design, a deterministic and broadly applicable framework that replaces the rigid block structure of Steiner systems with a flexible interweaved family structure. The IC design constructs-controlled overlaps among file groups and assigns tasks through clique-like intersections induced by these groups.
color:#002060;mso-ansi-language:EN-US">For broad regimes of (n), (d), and (N), the IC design achieves a communication cost [pi_{mathbf X}asympfrac{n}{N^{1/d}},]
color:#002060;mso-ansi-language:EN-US">while matching converse bounds show that no allocation scheme can improve this scaling beyond constant factors. Hence, the proposed design achieves the optimal partitioning gain of order (N^{1/d}), while maintaining bounded computation imbalance. A key feature of the construction is that file placement is blind to (mathbf X), allowing the same allocation to support multiple decompositions without reshuffling data.
color:#002060;mso-ansi-language:EN-US">The thesis further establishes limits for hypergraph edge partitioning under independent edge sampling, where each potential hyperedge may be retained with its own probability. This model captures heterogeneous, sparse, and structured task sets beyond dense complete hypergraphs. Under mild density conditions, the optimal maximum vertex footprint remains of order (n/N^{1/d}) with high probability. The analysis also extends to non-uniform hypergraphs of bounded rank, showing that the same scaling law persists when hyperedges have sizes up to (d).
color:#002060;mso-ansi-language:EN-US">Finally, the thesis investigates Hamiltonian decompositions of complete uniform hypergraphs and provides explicit generator-based constructions for broad parameter regimes, including prime (n) and (d
color:#002060;mso-ansi-language:EN-US">Overall, this thesis shows that carefully constructed combinatorial designs provide deterministic, scalable, and theoretically grounded solutions for distributed computation and hypergraph partitioning. By connecting IC structures, Steiner systems, probabilistic converse bounds, and Hamiltonian decompositions, it develops a unified view of communication--computation tradeoffs and moves beyond heuristic partitioning methods toward explicit constructions with guarantees.
