color:#002060">Distributed computing has emerged as a key enabler of modern communication and data-driven systems and networks, supporting large-scale applications such as wireless networks, machine learning, and real-time data processing. As data volumes and computational demands continue to grow, distributing computations across multiple users and processing nodes has become increasingly essential. In such systems, servers must collaboratively execute computational tasks while exchanging intermediate results over communication links with limited bandwidth. This intrinsic interplay between local computation in servers and information transmission from the servers to the user(s) leads to a fundamental challenge: how to efficiently balance computation and communication costs in multi-user distributed computing systems, which naturally introduces a trade-off between computation and communication costs.
color:#002060;mso-ansi-language:DE">
color:#002060">The existing approaches mainly studied this trade-off for linear and linearly-separable computations, and matrix multiplications. However, we examine a broader class of functions (non-linearly separable functions) as well by leveraging their structural properties. Particularly, this thesis investigates the communication-computation trade-off in a distributed computing framework with a master node that coordinates multiple servers to perform user demand(s) through three complementary approaches, detailed below.
DE">
color:#002060">Sensitivity-based Approach:
DE">
We study the role of the influence of datasets in the distributed computation of Boolean functions. By adopting a sensitivity-based perspective, we show that the placement of input datasets across servers fundamentally impacts both computation and communication costs. Leveraging tools from Boolean function analysis, we derive bounds and design schemes that enable more efficient task allocation than the state of the art by prioritizing highly influential datasets, thereby reducing redundant computations and communication overheads.
DE">
color:#002060">Sparse Tensor Factorization Approach:
DE">
We address the problem of non-linearly separable distributed computation by introducing a sparse tensor factorization framework. In this setting, users demand arbitrary real-valued multivariate polynomials, whose coefficients are modeled by high-dimensional tensors. We develop achievable schemes based on fixed-support tensor decompositions and structured multi-dimensional tiling, complemented by combinatorial assignment techniques that eliminate redundant computations across servers. This approach significantly reduces the required number of servers compared to classical matrix factorization-based methods, highlighting the importance of exploiting higher-dimensional structure in distributed systems.
color:#002060;mso-ansi-language:DE">
color:#002060">Coded Computing for Secure Matrix Multiplication:
DE">
We consider distributed matrix multiplication in dynamic environments with straggler and secrecy constraints, motivated by applications in vehicular networks. We propose a novel coded computation scheme that incorporates structured distributed source coding into polynomial-based coded distributed computing. The resulting framework achieves both resilience to straggling servers and protection against information leakage, enabling efficient and secure distributed computation.
color:#002060;mso-ansi-language:DE">
color:#002060">Overall, this thesis establishes new connections between distributed computing, Boolean function analysis, tensor-theoretic methods, information theory, coding theory, and vehicular networks.
DE">
