We consider polynomial codes for private distributed matrix multiplication (PDMM/SDMM). Existing codes for PDMM are either specialized for the outer product partitioning (OPP), or inner product partitioning (IPP), or are valid for the more general grid partitioning (GP). We design extension operations that can be applied to a large class of OPP code designs to extend them to the GP case. Applying them to existing codes improves upon the state-of-the-art for certain parameters. Additionally, we show that the GP schemes resulting from extension fulfill additional combinatorial constraints, potentially limiting their performance. We illustrate this point by presenting a new GP scheme that does not adhere to these constraints and outperforms the state-of-the-art for a range of parameters.

Federated learning (FL) shows great promise in large-scale machine learning but introduces new privacy and security challenges. We propose ByITFL and LoByITFL, two novel FL schemes that enhance resilience against Byzantine users while preventing eavesdroppers from learning users’ private data. To ensure privacy and Byzantine resilience, our schemes are built on having a small representative dataset available to the federator and crafting a discriminator function allowing mitigating corrupt users’ contributions. ByITFL employs Lagrange coded computing and re-randomization, making it the first Byzantine-resilient FL scheme with perfect Information-Theoretic (IT) privacy, though at the cost of a significant communication overhead. LoByITFL, on the other hand, achieves Byzantine resilience and IT privacy at a significantly reduced communication cost, but requires a Trusted Third Party (TTP), used only before training in a one-time initialization phase. We provide theoretical guarantees of privacy and Byzantine resilience, along with convergence guarantees and experimental results validating our findings.

DNA labelingis a tool in molecular biology and biotechnology to visualize, detect, and study DNA at the molecular level. In this process, a DNA molecule islabeledby a set of specific patterns, referred to aslabels, and is then imaged. The resulting image is modeled as an (ℓ + 1)-ary sequence, where ℓ is the number of labels, in which any non-zero symbol indicates the appearance of the corresponding label in the DNA molecule. Thelabeling capacityrefers to the maximum information rate that can be achieved by the labeling process for any given set of labels. The main goal of this paper is to study the minimum number of labels of the same length required to achieve the maximum labeling capacity of 2 for DNA sequences or log2qfor an arbitrary alphabet of sizeq. The solution to this problem requires the study of path unique subgraphs of the de Bruijn graph with the largest number of edges. We provide upper and lower bounds on this value. We draw new connections to existing literature that let us prove an asymptotic result as the label length tends to infinity.

We present novel constructions of polynomial codes for private distributed matrix multiplication (PDMM/SDMM) using outer product partitioning (OPP). We extend the degree table framework from the literature to cyclic-addition degree tables (CATs). By using roots of unity as evaluation points, we enable modulo-addition in the table. Based on CATs, we present an explicit construction, called CAT$_{\mathrm{x}}$, that requires fewer workers than existing schemes in the low-privacy regime. Additionally, we present new families of schemes based on conventional degree tables, called GASP${}_{\text{rs}}$and DOG$_{\text{rs}}$, that outperform the state-of-the-art for a wide range of parameters.

In federated learning, a federator coordinates the training of a model, e.g., a neural network, on privately owned data held by several participating clients. The gradient descent algorithm, a well-known and popular iterative optimization procedure, is run to train the model. Every client computes partial gradients based on their local data and sends them to the federator, which aggregates the results and updates the model. Privacy of the clients’ data is a major concern. In fact, it is shown that observing the partial gradients can be enough to reveal the clients’ data. Existing literature focuses on private aggregation schemes that tackle the privacy problem in federated learning in settings where all users are connected to each other and to the federator. In this paper, we consider a hierarchical wireless system architecture in which the clients are connected to base stations; the base stations are connected to the federator either directly or through relays. We examine settings with and without relays, and derive fundamental limits on the communication cost under information-theoretic privacy with different collusion assumptions. We introduce suitable private aggregation schemes tailored for these settings whose communication costs are multiplicative factors away from the derived bounds.

We consider gradient coding in the presence of an adversary controlling so-called malicious workers trying to corrupt the computations. Previous works propose the use of MDS codes to treat the responses from malicious workers as errors and correct them using the error-correction properties of the code. This comes at the expense of increasing the replication, i.e., the number of workerseach partial gradientis computed by. In this work, we propose a way to reduce the replication to$ {s} +1$instead of$2 {s} +1$in the presence ofsmalicious workers. Our method detects erroneous inputs from the malicious workers, transforming them into erasures. This comes at the expense ofsadditional local computations at the main node and additional rounds of light communication between the main node and the workers. We define a general framework and give fundamental limits for fractional repetition data allocations. Our scheme is optimal in terms of replication and local computation and incurs a communication cost that is asymptotically, in the size of the dataset, a multiplicative factor away from the derived bound. We furthermore show how additional redundancy can be exploited to reduce the number of local computations and communication cost, or, alternatively, tolerate straggling workers.

Federated edge learning (FEEL) has emerged as a core paradigm for large-scale optimization. However, FEEL still suffers from a communication bottleneck due to the transmission of high-dimensional model updates from the clients to the federator. Over-the-air computation (AirComp) leverages the additive property of multiple-access channels by aggregating the clients’ updates over the channel to save communication resources. While analog uncoded transmission can benefit from the increased signal-to-noise ratio (SNR) due to the simultaneous transmission of many clients, potential errors may severely harm the learning process for small SNRs. To alleviate this problem, channel coding approaches were recently proposed for AirComp in FEEL. However, their error-correction capability degrades with an increasing number of clients. We propose a digital lattice-based code construction with constant error-correction capabilities in the number of clients, and compare to nested-lattice codes, well-known for their optimal rate and power efficiency in the point-to-point AWGN channel.

DNA labeling is a tool in molecular biology and biotechnology to visualize, detect, and study DNA at the molec-ular level. In this process, a DNA molecule is labeled by a set of specific patterns, referred to as labels, and is then imaged. The resulting image is modeled as an$(\ell+1)$-ary sequence, where$\ell$is the number of labels, in which any nonzero symbol indicates the appearance of the corresponding label in the DNA molecule. The labeling capacity refers to the maximum information rate that can be achieved by the labeling process for any given set of labels. The main goal of this paper is to study the minimum number of labels of the same length required to achieve the maximum labeling capacity of 2 for DNA sequences or$\log_{2}q$for an arbitrary alphabet of size$q$. The solution to this problem requires the study of path unique subgraphs of the de Bruijn graph with the largest number of edges. We provide upper and lower bounds on this value.

We tackle the problem of Byzantine errors in dis-tributed gradient descent within the Byzantine-resilient gradient coding framework. Our proposed solution can recover the exact full gradient in the presence of$s$malicious workers with a data replication factor of only$s$+ 1. It generalizes previous solutions to any data assignment scheme that has a regular replication over all data samples. The scheme detects malicious workers through additional interactive communication and a small number of local computations at the main node, leveraging group-wise comparisons between workers with a provably optimal grouping strategy. The scheme requires at most$s$interactive rounds that incur a total communication cost logarithmic in the number of data samples.

Federated learning (FL) shows great promise in large-scale machine learning but brings new risks in terms of privacy and security. We propose ByITFL, a novel scheme for FL that provides resilience against Byzantine users while keeping the users' data private from the federator and private from other users. Our scheme builds on the preexisting non-private FLTrust scheme, which tolerates malicious users through trust scores (TS) that attenuate or amplify the users' gradient updates. The trust scores are based on the ReLU function, which we approximate by a polynomial. The distributed and privacy-preserving computation in ByITFL is designed using a combination of Lagrange coded computing, verifiable secret sharing and re-randomization steps. ByITFL is the first Byzantine resilient scheme for FL with full information-theoretic privacy.

Federated learning collaboratively trains a neural network on privately owned data held by several participating clients. The gradient descent algorithm, a well-known and popular iterative optimization procedure, is run to train the neural network. Every client uses its local data to compute partial gradients and sends it to the federator which aggregates the results. Privacy of the clients’ data is a major concern. In fact, observing the partial gradients can be enough to reveal the clients’ data. Private aggregation schemes have been investigated to tackle the privacy problem in federated learning where all the users are connected to each other and to the federator. In this paper, we consider a wireless system architecture where clients are only connected to the federator via base stations. We derive fundamental limits on the communication cost when information-theoretic privacy is required, and introduce and analyze a private aggregation scheme tailored for this setting.

We consider gradient coding in the presence of an adversary controlling so-called malicious workers trying to corrupt the computations. Previous works propose the use of MDS codes to treat the inputs of the malicious workers as errors and correct them using the error-correction properties of the code. This comes at the expense of increasing the replication, i.e., the number of workers each partial gradient is computed by. In this work, we reduce replication by proposing a method that detects the erroneous inputs from the malicious workers, hence transforming them into erasures. For s malicious workers, our solution can reduce the replication to s+1 instead of 2s+1 for each partial gradient at the expense of only s additional computations at the main node and additional rounds of light communication between the main node and the workers. We give fundamental limits of the general framework for fractional repetition data allocation. Our scheme is optimal in terms of replication and local computation but incurs a communication cost that is asymptotically, in the size of the dataset, a multiplicative factor away from the derived bound.