In real-world datasets, leveraging the low-rank and sparsity properties enables developing efficient algorithms across a diverse array of data-related tasks, including compression, compressed sensing, matrix completion, etc. Notably, these two properties often coexist in certain real-world datasets, especially in Boolean datasets and quantized real-valued datasets. To harness the advantages of low-rank and sparsity simultaneously, we adopt a technique inspired by compressed sensing and Boolean matrix completion. Our approach entails compressing a low-rank sparse Boolean matrix by performing inner product operations with a randomly generated Boolean matrix. We then propose a decoding algorithms based on message-passing techniques to recover the original matrix. Our experiments demonstrate superior recovery performance of our proposed algorithms compared to Boolean matrix completion, with equal measurement requirements.

Consider an $n$-dimensional binary feature vector with $k$ non-zero entries. The vector can be interpreted as the incident vector corresponding to $n$ items out of which $k$ items are \emph{defective}. The \emph{quantitative group testing} (QGT) problem aims at learning this binary feature vector by queries on subsets of the items that return the total number of defective items. We consider this problem under the \emph{non-adaptive} scenario where the queries on subsets are designed collectively and can be executed in parallel. Most of the existing efficient non-adaptive algorithms for the sublinear regime where $k = n^\alpha$ with $0 < \alpha < 1$ fall short of the information-theoretic lower bound, with a multiplicative gap of $\log k$. Recently, a near-optimal non-adaptive algorithm with a decoding complexity of $O(n^3)$ closed this gap. In this work, we present a concatenated construction method yielding a non-adaptive algorithm with a decoding complexity of $O(n^{2\alpha} + n \log^2 n)$. The probability of decoding failure is analyzed by establishing a connection between the QGT problem and the so-called \emph{balls into bins} problem. Our algorithm reduces the gap between the information-theoretic and computational bound for the number of required queries/tests from $\log k$ to $\log \log k$. This narrows the gap in the number of tests for non-adaptive algorithms within the class of algorithms with $o(n^2)$ decoding complexity. Moreover, although our algorithm exhibits a $\log \log k$ gap in terms of the number of tests, it is surpassed by the existing asymptotically optimal construction only in scenarios where $k$ is exceptionally large for moderate values of $\alpha$, such as $k > 10^{27}$ for $\alpha = 0.7$, thereby highlighting the practical applicability of our proposed concatenated construction.

The aim of quantitative group testing problem is to recover$k$defective items from a set of$n$items using minimal number of quantitative/additive group tests, where each test reveals the number of defective items present in the group. Fully adaptive strategies have been proposed and shown to, in general, require significantly fewer measurements. In the sublinear regime, where$k=n^{\alpha}$for$0 < \alpha < 1$, for instance, this means a gain proportional to$\alpha \log n$. However, this gain is obtained at the cost of significant complexity associated with adapting tests to previous outcomes. This paper introduces a family of low-complexity strategies with efficient construction and decoding. These strategies adapt tests only in stages, allowing for a flexible trade-off between the number of stages, i.e., the complexity cost of adaptation, and the overall number of tests i.e., the adaptivity gain. Specifically, our algorithm matches the state-of-the-art adaptive algorithm in terms of the number of measurements while reducing the required number of stages by a multiplicative factor of$1-\alpha$. Our results demonstrates that a small number of stages can lead to substantial improvements over non-adaptive strategies. Furthermore, in comparison to existing non-adaptive algorithms, our algorithm achieves a 47% improvement in the overall number of tests, with the addition of just one stage.

Distributed computing has attracted significant recent attention for speeding up large-scale computations by disseminating computational jobs from a central master node across several worker nodes/servers. However, worker nodes are often untrusted and can also collude to gain unauthorized access to sensitive data. Hence, sharing sensitive data with them raises data privacy concerns. Coded computing has emerged as a promising framework for speeding up distributed computing and can be also adapted to address security and privacy concerns utilizing tools from secret sharing and multi-party computing. However, ensuring perfect information-theoretic privacy imposes a strict threshold on the maximum number of colluding workers the protocol can tolerate and, also, necessitates quantizing/mapping data to finite fields. Differential privacy is a widely accepted practical measure to capture the privacy leakage of the shared data. The mainstream approach is then to add perturbations to the data via randomized mechanisms. In this paper, we revisit coded computing, and especially when it is adapted to handle real-valued data, and analyze the privacy guarantees through the lens of differential privacy in terms of the (ϵ,δ)-differential privacy metric, for the first time in the literature. All the computations are done over the field of real/complex numbers and data privacy, in terms of differential privacy, is attained by adding noise terms in a certain structured way. In particular, the noise is added through the secret sharing mechanism (which can be, in principle, decoded and cancelled out at the master) as means of ensuring differential privacy. Furthermore, we propose a differentially private distributed matrix multiplication protocol for matrix multiplications that keeps the privacy of data in the worst adversarial case.

We consider the low rank matrix completion problem over finite fields. This problem has been extensively studied in the domain of real/complex numbers, however, to the best of authors’ knowledge, there exists merely one efficient algorithm to tackle the problem in the binary field, due to Saunderson et al. [1]. In this paper, we improve upon the theoretical guarantees for the algorithm provided in [1]. Furthermore, we formulate a new graphical model for the matrix completion problem over the finite field of size q, ${\mathbb{F}_q}$, and present a message passing (MP) based approach to solve this problem. The proposed algorithm is the first one for the considered matrix completion problem over finite fields of arbitrary size. Our proposed method has a significantly lower computational complexity, reducing it from O(n2r+3) in [1] down to O(n2) (where, the underlying matrix has dimension n × n and r denotes its rank), while also improving the performance.

In this paper, we study the quantitative group testing problem, also known as the heavy hitter detection problem and the coin weighing problem, in a non-adaptive setting. In this problem, the aim is to recover k defective items from a group of n items with the smallest possible number of quantitative/additive tests, where each such test returns the number of defective items participating in the test. In the non-adaptive setting, that we study in this paper, all tests are designed at once and can be, in principle, run in parallel. We establish a novel construction method for designing non-adaptive test matrices with a nested structure inspired by the Plotkin concatenation in the coding theory literature. Our proposed algorithm identifies k defective items among the collection of n items with high probability using $k(1 + o(1))\log \left( {\frac{n}{k}} \right)$ non-adaptive tests in the sub-linear regime of k = o(n). Furthermore, our analysis demonstrates that the probability of decoding failure approaches zero exponentially in k as k, n → ∞. Our approach outperforms existing state-of-the-art methods for designing non-adaptive test schemes with efficient decoders for the quantitative group testing problem in terms of the required number of measurements.

Due to the surge of cloud-assisted AI services, the problem of designing resilient prediction serving systems that can effectively cope with stragglers and minimize response delays has attracted much interest. The common approach for tackling this problem is replication which assigns the same prediction task to multiple workers. This approach, however, is inefficient and incurs significant resource overheads. Hence, a learning-based approach known as parity model (ParM) has been recently proposed which learns models that can generate ``parities’’ for a group of predictions to reconstruct the predictions of the slow/failed workers. While this learning-based approach is more resource-efficient than replication, it is tailored to the specific model hosted by the cloud and is particularly suitable for a small number of queries (typically less than four) and tolerating very few stragglers (mostly one). Moreover, ParM does not handle Byzantine adversarial workers. We propose a different approach, named Approximate Coded Inference (ApproxIFER), that does not require training any parity models, hence it is agnostic to the model hosted by the cloud and can be readily applied to different data domains and model architectures. Compared with earlier works, ApproxIFER can handle a general number of stragglers and scales significantly better with the number of queries. Furthermore, ApproxIFER is robust against Byzantine workers. Our extensive experiments on a large number of datasets and model architectures show significant degraded mode accuracy improvement by up to 58% over ParM.

single,double We consider the critical problems of distributed computing and learning over data while keeping it private from the computational servers. The state-of-the-art approaches to this problem rely on quantizing the data into a finite field, so that the cryptographic approaches for secure multiparty computing can then be employed. These approaches, however, can result in substantial accuracy losses due to fixed-point representation of the data and computation overflows. To address these critical issues, we propose a novel algorithm to solve the privacy-preserving distributed computing problem when data is in the analog domain, e.g., the field of real/complex numbers. We characterize the privacy of the data from both information-theoretic and cryptographic perspectives, while establishing a connection between the two notions in the analog domain. More specifically, the well-known connection between the distinguishing security (DS) and the mutual information security (MIS) metrics is extended from the discrete domain to the analog domain. This is then utilized to bound the amount of information about the data leaked to the servers in our protocol, in terms of the DS metric, using well-known results on the capacity of single-input multiple-output (SIMO) channel with correlated noise. It is shown how the proposed framework can be adopted to do computation tasks when data is represented using floating-point numbers. We then show that this leads to a fundamental trade-off between the privacy level of data and accuracy of the result. By extending the setup to distributed learning, we show how to train a machine learning model using the proposed algorithm while keeping the data as well as the trained model private. Then numerical results are shown for experiments on several datasets. Furthermore, experimental advantages are shown comparing to fixed-point implementations over finite fields.

We provide a novel framework to study subspace codes for non-coherent communications in wireless networks. To this end, ananalog operator channelis defined with inputs and outputs being subspaces of${ \mathbb C}^{n}$. Then a certain distance is defined to capture the performance of subspace codes in terms of their capability to recover from interference and rank-deficiency of the network. We also study the robustness of the proposed model with respect to an additive noise. Furthermore, we propose a new approach to construct subspace codes in the analog domain, also regarded as Grassmann codes, by leveraging polynomial evaluations over finite fields together with characters associated to finite fields that map their elements to the unit circle in the complex plane. The constructed codes, referred to as character-polynomial (CP) codes, are shown to perform better comparing to other existing constructions of Grassmann codes in terms of the trade-off between the rate and the normalized minimum distance, for a wide range of values for$n$.

We consider the problem of coded computing, where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations to obtain the side information. This side information is then utilized to prune the output of the list decoder and uniquely recover the true outcome. We further propose folded Lagrange coded computing (FLCC) to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two compared to that of LCC.

We provide a new algebraic construction for packing subspaces in complex Grassmannian space with respect to the chordal distance metric. The proposed method extends the construction of character-polynomial (CP) subspace codes, recently proposed by the authors, to higher dimensions. Our results indicate the superiority of the packings derived from CP codes in the real Grassmannian space compared with existing explicit construction. Furthermore, we propose a concatenation method in Grassmannian space and characterize the rate and the minimum distance of a concatenated Grassmann code in terms of those of its underlying inner and outer codes. This result is then utilized to arrive at the counterpart of Zyablov bound in Grassmannian space. Finally, we construct Grassmann codes with asymptotically large blocklength simultaneously attaining non-vanishing rate and normalized minimum distance. In particular, we propose a family of concatenated Grassmann codes having CP inner codes that surpass the Zyablov bound in the low-rate regime.

The state-of-the-art approaches to privacy-preserving coded computing rely on quantizing the data into a finite field, so that Shamir's secret sharing can be employed. Such coded computing solutions, however, are not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of certain coded computing schemes to the analog domain. This includes distributed polynomial evaluation and Lagrange coded computing (LCC) that are widely used in the literature. All the operations in the proposed protocols are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in our proposed protocols, against any subset of colluding servers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, fundamental trade-offs between the accuracy of the outcome and their privacy level are observed in the analog domain and are numerically evaluated. Moreover, we implement analog LCC (ALCC) to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.

We provide a precise framework to study subspace codes for non-coherent communications in wireless networks. To this end, an analog operator channel is defined with inputs and outputs being subspaces of Cn. Then a certain distance is defined to capture the performance of subspace codes in terms of their capability to recover from interference and rank-deficiency of the network. We also study the robustness of the proposed model with respect to additive noise. Furthermore, we propose a new approach to construct subspace codes in the analog domain, also regarded as Grassmann codes, by leveraging polynomial evaluations over finite fields together with characters associated to finite fields that map their elements to the unit circle in the complex plane. The constructed codes, referred to as characterpolynomial (CP) codes, are shown to perform better compared to other existing constructions of Grassmann codes in terms of the trade-off between the rate and the normalized minimum distance, for a wide range of values for n.

We consider the problem of coded distributed computing where a large linear computational job, such as a matrix multiplication, is divided into k smaller tasks, encoded using an (n, k) linear code, and performed over n distributed nodes. The goal is to reduce the average execution time of the computational job. We provide a connection between the problem of characterizing the average execution time of a coded distributed computing system and the problem of analyzing the error probability of codes of length n used over erasure channels. Accordingly, we present closed-form expressions for the execution time using binary random linear codes and the best execution time any linear-coded distributed computing system can achieve. It is also shown that there exist good binary linear codes that attain, asymptotically, the best performance any linear code, not necessarily binary, can achieve. We also investigate the performance of coded distributed computing systems using polar and Reed-Muller (RM) codes that can benefit from low-complexity decoding, and superior performance, respectively, as well as explicit constructions. The proposed framework in this paper can enable efficient designs of distributed computing systems given the rich literature in the channel coding theory.

A distributed secret sharing system is considered that consists of a dealer, n storage nodes, and m users. Each user is given access to a certain subset of storage nodes where it can download the data. The dealer wants to securely convey a specific secret sjto user j via storage nodes, for j = 1, 2,..., m, in such a way that no user gets any information about other users' secrets in an information-theoretic sense. To this end, we propose to study protocols where the dealer encodes secrets into several secret shares and loads them into the storage nodes. Given a certain number of storage nodes we find the maximum number of users that can be served in such protocols and construct schemes that achieve this. We further define two major properties for such distributed secret sharing systems; communication complexity is defined as the total amount of data that needs to be downloaded by users in order to reconstruct their secrets; and storage overhead is defined as the total amount of data loaded by the dealer into the storage nodes normalized by the total size of secrets. Lower bounds on minimum communication complexity and storage overhead are characterized given any n and m. Furthermore, we construct distributed secret sharing protocols, under certain conditions on the system parameters, that attain these lower bounds thereby providing schemes that are optimal in terms of both the communication complexity and storage overhead.