Mimicking the idea of the generalized Hamming weight of linear codes, we introduce a new lattice invariant, the generalized theta series. Applications range from identifying stable lattices to the lattice isomorphism problem. Moreover, we provide counterexamples for the secrecy gain conjecture on isodual lattices, which claims that the ratio of the theta series of an isodual (and more generally, formally unimodular) lattice by the theta series of the integer lattice ${\mathbb{Z}^n}$ is minimized at a (unique) symmetry point.

We investigate practical finite-blocklength classical–quantum channel coding over the quantum amplitude damping channel (ADC), aiming to transmit classical information reliably through quantum outputs. Our findings indicate that for any finite blocklength, a naive (uncoded) approach fails to offer any advantage over the ADC. Instead, sophisticated encoding strategies that leverage both classical error-correcting codes and quantum input states are crucial for realizing quantum performance gains at finite blocklengths.

We consider the problem of communication-constrained collaborative personalized mean estimation under a privacy constraint in an environment of several agents continuously receiving data according to arbitrary unknown agent-specific distributions. A consensus-based algorithm is studied under the framework of differential privacy in order to protect each agent’s data. We give a theoretical convergence analysis of the proposed consensus-based algorithm for any bounded unknown distributions on the agents’ data, showing that collaboration provides faster convergence than a fully local approach where agents do not share data, under an oracle decision rule and under some restrictions on the privacy level and the agents’ connectivity, which illustrates the benefit of private collaboration in an online setting under a communication restriction on the agents. The theoretical faster-than-local convergence guarantee is backed up by several numerical results.

We consider the problem of collaborative personalized mean estimation under a privacy constraint in an environment of several agents continuously receiving data according to arbitrary unknown agent-specific distributions. In particular, we provide a method based on hypothesis testing coupled with differential privacy and data variance estimation. Two differential privacy mechanisms protecting the releases of each agent’s current sample mean and two data variance estimation schemes are proposed, and we provide a theoretical convergence analysis of the proposed algorithm for any bounded unknown distributions on the agents’ data, showing that collaboration provides faster convergence than a fully local approach where agents do not share data. Moreover, we provide analytical performance curves for the case with an oracle class estimator, i.e., the class structure of the agents, where agents receiving data from distributions with the same mean are considered to be in the same class, is known. The theoreticalfaster-than-localconvergence guarantee is backed up by extensive numerical results showing that for a considered scenario with 200 agents from two or three classes the proposed approach indeed converges much faster than a fully local approach, and performs comparably to the ideal (all-data-public) case. This illustrates the benefit of private collaboration in an online setting.

This paper explores differentially-private federated learning (FL) across time-varying databases, delving into a nuanced three-way tradeoff involving age, accuracy, and differential privacy (DP). Emphasizing the potential advantages of scheduling, we propose an optimization problem aimed at meeting DP requirements while minimizing the loss difference between the aggregated model and the model obtained without DP constraints. To harness the benefits of scheduling, we in-troduce an age-dependent upper bound on the loss, leading to the development of an age-aware scheduling design. Simulation results underscore the superior performance of our proposed scheme compared to FL with classic DP, which does not consider scheduling as a design factor. This research contributes insights into the interplay of age, accuracy, and DP in FL, with practical implications for scheduling strategies.

Recently, a design criterion depending on a lattice’s volume and theta series, called the secrecy gain, was proposed to quantify the secrecy-goodness of the applied lattice code for the Gaussian wiretap channel. To address the secrecy gain of Construction A4 lattices from formally self-dual$ \mathbb {Z}_{4}$-linear codes, i.e., codes for which the symmetrized weight enumerator (swe) coincides with the swe of its dual, we present new constructions of$ \mathbb {Z}_{4}$-linear codes which are formally self-dual with respect to the swe. For even lengths, formally self-dual$ \mathbb {Z}_{4}$-linear codes are constructed from nested binary codes and double circulant matrices. For odd lengths, a novel construction called odd extension from double circulant codes is proposed. Moreover, the concepts of Type I/II formally self-dual codes/unimodular lattices are introduced. Next, we derive the theta series of the formally unimodular lattices obtained by Construction A4 from formally self-dual$ \mathbb {Z}_{4}$-linear codes and describe a universal approach to determine their secrecy gains. The secrecy gain of Construction A4 formally unimodular lattices obtained from formally self-dual$ \mathbb {Z}_{4}$-linear codes is investigated, both for even and odd dimensions. Numerical evidence shows that for some parameters, Construction A4 lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Results concerning the flatness factor, another security criterion widely considered in the Gaussian wiretap channel, are also discussed.

We propose a new interpolation-based error decoding algorithm for (n,k) Reed-Solomon (RS) codes over a finite field of size q, where n = q − 1 is the length and k is the dimension. In particular, we employ the fast Fourier transform (FFT) together with properties of a circulant matrix associated with the error interpolation polynomial and some known results from elimination theory in the decoding process. The asymptotic computational complexity of the proposed algorithm for correcting any $t \leq \left\lfloor {\frac{{n - k}}{2}} \right\rfloor$ errors in an (n,k) RS code is of order ${\mathcal{O}}\left( {t{{\log }^2}t} \right)$ and ${\mathcal{O}}\left( {n{{\log }^2}n\log \log n} \right)$ over FFT-friendly and arbitrary finite fields, respectively, achieving the best currently known asymptotic decoding complexity, proposed for the same set of parameters.

We study the problem of pliable private information retrieval with side information (PPIR-SI) for the single server case. In PPIR, the messages are partitioned into nonoverlapping classes and stored in a number of noncolluding databases. The user wishes to retrieve any one message from a desired class while revealing no information about the desired class identity to the databases. In PPIR-SI, the user has prior access to some side information in the form of messages from different classes and wishes to retrieve any one new message from a desired class, i.e., the message is not included in the side information set, while revealing no information about the desired class to the databases. We characterize the capacity of (linear) single-server PPIR-SI for the case where the user’s side information is unidentified, i.e., the user is oblivious of the identities of its side information messages and the database structure. We term this case PPIR-USI. Surprisingly, we show that having side information, in PPIR-USI, is disadvantageous, in terms of the download rate, compared to PPIR.

We consider the problem of collaborative personalized mean estimation under a privacy constraint in an environment of several agents continuously receiving data according to arbitrary unknown agent-specific distributions. In particular, we provide a method based on hypothesis testing coupled with differential privacy. Two privacy mechanisms are proposed and we provide a theoretical convergence analysis of the proposed algorithm for any bounded unknown distributions on the agents’ data. Numerical results show that for a considered scenario the proposed approach converges much faster than a fully local approach where agents do not share data, and performs comparably to ideal performance where all data is public. This illustrates the benefit of private collaboration in an online setting.

In contrast to binary codes, odd-length self-dual codes exist over the integers modulo 4. Lately, the use of lattices constructed from codes over ℤ4to guarantee secure communication in a Gaussian wiretap channel was proposed and shown to exceed the performance of lattices from binary codes. This performance is measured regarding the secrecy gain, a criterion that depends on a lattice’s volume and theta series. Formally unimodular lattices, i.e., lattices with the same theta series as their dual, have presented promising results with respect to the secrecy gain. While previous contributions in the literature were mainly focused on even-dimensional lattices, this paper addresses the secrecy gain of odd-dimensional formally unimodular lattices obtained from codes over ℤ4, together with a novel construction of such codes.

This paper introduces the family of lattice-like packings, which generalizes lattices, consisting of packings possessing periodicity and geometric uniformity. The subfamily of formally unimodular (lattice-like) packings is further investigated. It can be seen as a generalization of the unimodular and isodual lattices, and the Construction A formally unimodular packings obtained from formally self-dual codes are presented. Recently, lattice coding for the Gaussian wiretap channel has been considered. A measure called the secrecy function was proposed to characterize the eavesdropper’s probability of correctly decoding. The aim is to determine the global maximum value of the secrecy function, called (strong) secrecy gain. We further apply lattice-like packings to coset coding for the Gaussian wiretap channel and show that the family of formally unimodular packings shares the same secrecy function behavior as unimodular and isodual lattices. We propose a universal approach to determine the secrecy gain of a Construction A formally unimodular packing obtained from a formally self-dual code. From the weight distribution of a code, we provide a necessary condition for a formally self-dual code such that its Construction A formally unimodular packing is secrecy-optimal. Finally, we demonstrate that formally unimodular packings/lattices can achieve higher secrecy gain than the best-known unimodular lattices.

Lattice coding for the Gaussian wiretap channel is considered, where the goal is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called secrecy gain was proposed as a design criterion to quantify the secrecy-goodness of the applied lattice code. In this paper, the theta series of the so-called formally unimodular lattices obtained by Construction A4from codes over ${{\mathbb{Z}}_4}$ is derived, and we provide a universal approach to determine their secrecy gains. Initial results indicate that Construction A4lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Furthermore, a new code construction of formally self-dual ${{\mathbb{Z}}_4}$-linear codes is presented.

We consider straggler resiliency in decentralized learning using stochastic gradient descent under the notion of network differential privacy (DP). In particular, we extend the recently proposed framework of privacy amplification by decentralization by Cyffers and Bellet to include training latency—comprising both computation and communication latency. Analytical results on both the convergence speed and the DP level are derived for training over a logical ring for both a skipping scheme (which ignores the stragglers after a timeout) and a baseline scheme that waits for each node to finish before the training continues. Our results show a trade-off between training latency, accuracy, and privacy, parameterized by the timeout of the skipping scheme. Finally, results when training a logistic regression model on a real-world dataset are presented.

Private computation in a distributed storage system (DSS) is a generalization of the private information retrieval (PIR) problem. In such a setting, a user wishes to compute a function of$f$messages stored in$n$noncolluding coded databases, i.e., databases storing data encoded with an$[n,k]$linear storage code, while revealing no information about the desired function to the databases. We consider the problem of private linear computation (PLC) for coded databases. In PLC, a user wishes to compute a linear combination over the$f$messages while keeping the coefficients of the desired linear combination hidden from the databases. For a DSS setup where data is stored using a code from a particular family of linear storage codes, we derive an outer bound on the PLC rate, which is defined as the ratio of the desired amount of information and the total amount of downloaded information. In particular, the proposed converse is valid for any number of messages and linear combinations, and depends on the rank of the coefficient matrix obtained from all linear combinations. Further, we present a PLC scheme with rate equal to the outer bound and hence settle the PLC capacity for the considered class of linear storage codes. Interestingly, the PLC capacity matches the maximum distance separable coded capacity of PIR for the considered class of linear storage codes.

Private information retrieval protocols guarantee that a user canprivatelyandlosslesslyretrieve a single file from a database stored across multiple servers. In this work, we propose to simultaneously relax the conditions of perfect retrievability and privacy in order to obtain improved download rates when all files are stored uncoded on a single server. Information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the desired file. The main findings are: i) The derivation of the optimal tradeoff between download rate, distortion, and information leakage when the file size isinfinite. Closed-form expressions of the optimal tradeoff for the special cases of “no-leakage” and “no-privacy” are also given. ii) A novel approach based on linear programming (LP) to construct schemes for a finite file size and an arbitrary number of files. The proposed LP approach can be leveraged to find provably optimal schemes with corresponding closed-form expressions for the rate-distortion-leakage tradeoff when the database contains at most four bits. Finally, for a database that contains 320 bits, we compare two construction methods based on the LP approach with a nonconstructive scheme downloading subsets of files using a finite-length lossy compressor based on random coding.

We consider the problem of private polynomial computation (PPC) from a distributed storage system (DSS). In such setting a user wishes to compute a multivariate polynomial of degree at most$g$over$f$variables (or messages) stored in$n$noncolluding coded databases, i.e., databases storing data encoded with an$[n,k]$linear storage code, while revealing no information about the desired polynomial evaluation to the databases. For a DSS setup where data is stored using linear storage codes, we derive an outer bound on the PPC rate, which is defined as the ratio of the (minimum) desired amount of information and the total amount of downloaded information, and construct two novel PPC schemes. In the first scheme, we consider Reed-Solomon coded databases with Lagrange encoding, which leverages ideas from recently proposed star-product private information retrieval and Lagrange coded computation. The second scheme considers the special case of coded databases with systematic Lagrange encoding. Both schemes yield improved rates, while asymptotically, as$f\rightarrow \infty $, the systematic scheme gives a significantly better computation retrieval rate compared to all known schemes up to some storage code rate that depends on the maximum degree of the candidate polynomials.

We propose to extend the concept of private information retrieval by allowing for distortion in the retrieval process and relaxing the perfect privacy requirement at the same time. In particular, we study the tradeoff between download rate, distortion, and user privacy leakage, and show that in the limit of large file sizes this tradeoff can be captured via a novel information-theoretical formulation for datasets with a known distribution. Moreover, for scenarios where the statistics of the dataset is unknown, we propose a new deep learning framework by leveraging a generative adversarial network approach, which allows the user to learn efficient schemes from the data itself, minimizing the download cost. We evaluate the performance of the scheme on a synthetic Gaussian dataset as well as on the MNIST, CIFAR-10, and LSUN datasets. For the MNIST, CIFAR-10, and LSUN datasets, the data-driven approach significantly outperforms a nonlearning-based scheme which combines source coding with multiple file download.

Private information retrieval (PIR) protocols ensure that a user can download a file from a database without revealing any information on the identity of the requested file to the servers storing the database. While existing protocols strictly impose that no information is leaked on the file’s identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the perfect privacy requirement. We refer to such protocols as weakly-private information retrieval (WPIR) protocols. In particular, for the case of multiple noncolluding replicated servers, we study how the download rate, the upload cost, and the access complexity can be improved when relaxing the perfect privacy constraint. To quantify the information leakage on the requested file’s identity we consider mutual information (MI), worst-case information leakage, and maximal leakage (MaxL). We present two WPIR schemes, denoted by Scheme A and Scheme B, based on two recent PIR protocols and show that the download rate of the former can be optimized by solving a convex optimization problem. We also show that Scheme A achieves an improved download rate compared to the recently proposed scheme by Samyet al.under the so-called$\epsilon $-privacy metric. Additionally, a family of schemes based on partitioning is presented. Moreover, we provide an information-theoretic converse bound for the maximum possible download rate for the MI and MaxL privacy metrics under a practical restriction on the alphabet size of queries and answers. For two servers and two files, the bound is tight under the MaxL metric, which settles the WPIR capacity in this particular case. Finally, we compare the performance of the proposed schemes and their gap to the converse bound.

Private information retrieval protocols guarantee that a user can privately and losslessly retrieve a single file from a database stored across multiple servers. In this work, we propose to simultaneously relax the conditions of perfect retrievability and privacy in order to obtain improved download rates in the single server scenario, i.e., all files are stored uncoded on a single server. In particular, we derive the optimal tradeoff between download rate, distortion, and information leakage when the file size is infinite and the information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the requested file. Moreover, we present a novel approach based on linear programming to construct schemes for a finite file size and an arbitrary number of files. When the database contains at most four bits, this approach can be leveraged to find provably optimal schemes.

Weakly-private information retrieval (WPIR) is a variant of the private information retrieval problem in which a user wants to efficiently retrieve a file stored across a set of servers while tolerating some information leakage on the identity of the requested file to the servers. In this paper, we consider WPIR from a single-server database where the information leakage is measured in terms of the mutual information (MI) or maximal leakage (MaxL) privacy metrics. In particular, we establish a connection between the WPIR problem and rate-distortion theory, and fully characterize the optimal tradeoff between the download cost and the allowed information leakage under the MI and MaxL metrics, settling the single-server WPIR capacity.

Millimeter-wave (mmWave) communication is a promising technology to cope with the exponential increase in 5G data traffic. Such networks typically require a very dense deployment of base stations. A subset of those, so-called macro base stations, feature high-bandwidth connection to the core network, while relay base stations are connected wirelessly. To reduce cost and increase flexibility, wireless backhauling is needed to connect both macro to relay as well as relay to relay base stations. The characteristics of mmWave communication mandates new paradigms for routing and scheduling. The paper investigates scheduling algorithms under different interference models. To showcase the scheduling methods, we study the maximum throughput fair scheduling problem. Yet the proposed algorithms can be easily extended to other problems. For a full-duplex network under the no interference model, we propose an efficient polynomial-time scheduling method, the schedule-oriented optimization. Further, we prove that the problem is NP-hard if we assume pairwise link interference model or half-duplex radios. Fractional weighted coloring based approximation algorithms are proposed for these NP-hard cases. Moreover, the approximation algorithm parallel data stream scheduling is proposed for the case of half-duplex network under the no interference model. It has better approximation ratio than the fractional weighted coloring based algorithms and even attains the optimal solution for the special case of uniform orthogonal backhaul networks.

Private information retrieval (PIR) protocols make it possible to retrieve a file from a database without disclosing any information about the identity of the file being retrieved. These protocols have been rigorously explored from an information-theoretic perspective in recent years. While existing protocols strictly impose that no information is leaked on the file's identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the requirement of perfect privacy. In case the user is willing to leak some information on the identity of the retrieved file, we study how the PIR rate, as well as the upload cost and access complexity, can be improved. For the particular case of replicated servers, we propose two weakly-private information retrieval schemes based on two recent PIR protocols and a family of schemes based on partitioning. Lastly, we compare the performance of the proposed schemes.

We consider private polynomial computation (PPC) over noncolluding coded databases. In such a setting a user wishes to compute a multivariate polynomial of degree at most g over f variables (or messages) stored in multiple databases while revealing no information about the desired polynomial to the databases. We construct two novel PPC schemes, where the first is a generalization of our previous work in private linear computation for coded databases. In this scheme we consider Reed-Solomon coded databases with Lagrange encoding, which leverages ideas from recently proposed star-product private information retrieval and Lagrange coded computation. The second scheme considers the special case of coded databases with systematic Lagrange encoding. Both schemes yield improved rates compared to the best known schemes from the literature for a small number of messages, while in the asymptotic case the rates match.

We consider private information retrieval (PIR) for distributed storage systems with noncolluding nodes where data is stored using a non maximum distance separable (MDS) linear code. Recently, it was shown that when data is stored using certain non-MDS codes, the MDS-PIR capacity can be achieved, and is indeed the capacity of the system. In this paper, for storage codes not belonging to this class, we present a heuristic algorithm for their decomposition into punctured subcodes and a PIR protocol based on these punctured subcodes. The code decomposition is guided by the generalized Hamming weights of the storage code. We show that the proposed PIR protocol can achieve a larger PIR rate than that of all existing PIR protocols.

We consider the problem of private computation (PC) in a distributed storage system. In such a setting a user wishes to compute a function of f messages replicated across n noncolluding databases, while revealing no information about the desired function to the databases. We provide an information-theoretically accurate achievable PC rate, which is the ratio of the smallest desired amount of information and the total amount of downloaded information, for the scenario of nonlinear computation. For a large message size the rate equals the PC capacity, i.e., the maximum achievable PC rate, when the candidate functions are the f independent messages and one arbitrary nonlinear function of these. When the number of messages grows, the PC rate approaches an outer bound on the PC capacity. As a special case, we consider private monomial computation (PMC) and numerically compare the achievable PMC rate to the outer bound for a finite number of messages.

We propose three private information retrieval (PIR) protocols for distributed storage systems (DSSs), where data is stored using an arbitrary linear code. The first two protocols, named Protocol 1 and Protocol 2, achieve privacy for the scenario with noncolluding nodes. Protocol 1 requires a file size that is exponential in the number of files in the system, while Protocol 2 requires a file size that is independent of the number of files and is hence simpler. We prove that, for certain linear codes, Protocol 1 achieves the maximum distance separable (MDS) PIR capacity, i.e., the maximum PIR rate (the ratio of the amount of retrieved stored data per unit of downloaded data) for a DSS that uses an MDS code to store any given (finite and infinite) number of files, and Protocol 2 achieves the asymptotic MDS-PIR capacity (with infinitely large number of files in the DSS). In particular, we provide a necessary and a sufficient condition for a code to achieve the MDS-PIR capacity with Protocols 1 and 2 and prove that cyclic codes, Reed-Muller (RM) codes, and a class of distance-optimal local reconstruction codes achieve both the finite MDS-PIR capacity (i.e., with any given number of files) and the asymptotic MDS-PIR capacity with Protocols 1 and 2, respectively. Furthermore, we present a third protocol, Protocol 3, for the scenario with multiple colluding nodes, which can be seen as an improvement of a protocol recently introduced by Freij-Hollanti et al.. Similar to the noncolluding case, we provide a necessary and a sufficient condition to achieve the maximum possible PIR rate of Protocol 3. Moreover, we provide a particular class of codes that is suitable for this protocol and show that RM codes achieve the maximum possible PIR rate for the protocol. For all three protocols, we present an algorithm to optimize their PIR rates.

Millimeter-wave (mmWave) communication is a promising technology to cope with the expected exponential increase in data traffic in 5G networks. mmWave networks typically require a very dense deployment of mmWave base stations (mmBS). To reduce cost and increase flexibility, wireless backhauling is needed to connect the mmBSs. The characteristics of mmWave communication, and specifically its high directionality, imply new requirements for efficient routing and scheduling paradigms. We propose an efficient scheduling method, so-called schedule-oriented optimization, based on matching theory that optimizes QoS metrics jointly with routing. It is capable of solving any scheduling problem that can be formulated as a linear program whose variables are link times and QoS metrics. As an example of the schedule-oriented optimization, we show the optimal solution of the maximum throughput fair scheduling (MTFS). Practically, the optimal scheduling can be obtained even for networks with over 200 mmBSs. To further increase the runtime performance, we propose an efficient edge-coloring based approximation algorithm with provable performance bound. It achieves over 80% of the optimal max-min throughput and runs 5 to 100 times faster than the optimal algorithm in practice. Finally, we extend the optimal and approximation algorithms for the cases of multi-RF-chain mmBSs and integrated backhaul and access networks.

We propose a private information retrieval (PIR) protocol for distributed storage systems with noncolluding nodes where data is stored using an arbitrary linear code. An expression for the PIR rate, i.e., the ratio of the amount of retrieved data per unit of downloaded data, is derived, and a necessary and a sufficient condition for codes to achieve the maximum distance separable (MDS) PIR capacity are given. The necessary condition is based on the generalized Hamming weights of the storage code, while the sufficient condition is based on code automorphisms. We show that cyclic codes and Reed-Muller codes satisfy the sufficient condition and are thus MDS-PIR capacity-achieving.

An extension from the pairwise Hamming distance to the r-wise Hamming distance is presented. It can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code over the binary erasure channel (BEC). By noting that good codes always have large minimum r-wise Hamming distances for all r, a new design criterion for a code is introduced: the minimum r-wise Hamming distance. We then prove an upper bound for the minimum r-wise Hamming distance of an arbitrary code, called the generalized Plotkin bound, and provide a class of (nonlinear) codes that achieve the bound for every r.

We prove that a class of distance-optimal local reconstruction codes (LRCs), an important family of repair-efficient codes for distributed storage systems, achieve the maximum distance separable private information retrieval capacity for the case of noncolluding nodes. This particular class of codes includes Pyramid codes and other LRCs proposed in the literature.

We consider private information retrieval (PIR) for distributed storage systems (DSSs) with noncolluding nodes where data is stored using a non maximum distance separable (MDS) linear code. It was recently shown that if data is stored using a particular class of non-MDS linear codes, the MDS-PIR capacity, i.e., the maximum possible PIR rate for MDS-coded DSSs, can be achieved. For this class of codes, we prove that the PIR capacity is indeed equal to the MDS-PIR capacity, giving the first family of non-MDS codes for which the PIR capacity is known. For other codes, we provide asymmetric PIR protocols that achieve a strictly larger PIR rate compared to existing symmetric PIR protocols.

This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords M, can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the r-wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum r-wise Hamming distance satisfies a generalized r-wise Plotkin bound. The r-wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the r-wise Plotkin bound with equality for all r. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 <; δ <; 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the r-wise Hamming distance structure of the code. For a number of codewords M satisfying M ≤ 4 and an arbitrary finite blocklength n, the globally optimal codes (in the sense of minimizing the average error probability) are found. For M = 5 or M = 6 and an arbitrary finite blocklength n, the optimal codes are conjectured. For larger M, observations regarding the optimal design are presented, e.g., that good codes have a large r-wise Hamming distance structure for all r. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes.

In many applications that employ wireless sensor networks (WSNs), robustness of distributed inference against Byzantine attacks is important. In this work, distributed inference is considered when local sensors send M-ary data to the fusion center. The optimal Byzantine attack policy is then derived under the assumption that the Byzantine adversary has the knowledge of the statistics of local quantization outputs. Our analysis indicates that the fusion center can be blinded such that the detection error is as poor as a random guess when an adequate fraction of sensors are compromised.

The exact value of the average error probability of an arbitrary code (linear or nonlinear) using maximum likelihood decoding is studied on binary erasure channels (BECs) with arbitrary erasure probability 03.

In this paper, we re-introduce from our previous work [1] a new family of nonlinear codes, called weak flip codes, and show that its subfamily fair weak flip codes belongs to the class of equidistant codes, satisfying that any two distinct codewords have identical Hamming distance. It is then noted that the fair weak flip codes are related to the binary nonlinear Hadamard codes as both code families maximize the minimum Hamming distance and meet the Plotkin upper bound under certain blocklengths. Although the fair weak flip codes have the largest minimum Hamming distance and achieve the Plotkin bound, we find that these codes are by no means optimal in the sense of average error probability over binary symmetric channels (BSC). In parallel, this result implies that the equidistant Hadamard codes are also nonoptimal over BSCs. Such finding is in contrast to the conventional code design that aims at the maximization of the minimum Hamming distance. The results in this paper are proved by examining the exact error probabilities of these codes on BSCs, using the column-wise analysis on the codebook matrix.

The channel capacity of a noncoherent single-input multiple-output regular fading channel with memory and with feedback is investigated. The fading process is assumed to be a general stationary and ergodic random process of finite energy and finite differential entropy rate. The feedback is assumed to be noisefree (i.e., it is of infinite capacity), but causal. It is reported that the asymptotic capacity grows double-logarithmically in the power and that the second term in the asymptotic expansion, the fading number, is unchanged with respect to the same channel without feedback.

Optimal block-codes (in the sense of minimum average error probability, using maximum likelihood decoding) with a small number of codewords are investigated for the binary asymmetric channel (BAC), including the two special cases of the binary symmetric channel (BSC) and the Z-channel (ZC), both with arbitrary cross-over probabilities. For the ZC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two, three, and four codewords and conjectured in the case of five codewords. For the BSC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two and three codewords and conjectured in the case of four codewords. For a general BAC, the best codebooks under the assumption of a threshold decoder are derived for the case of two codewords. The derivation of these optimal codes relies on a new approach of constructing and analyzing the codebook matrix not rowwise (codewords), but columnwise. This new tool leads to an elegant definition of interesting code families that is recursive in the blocklength n and admits their exact analysis of error performance. This allows for a comparison of the average error probability between all possible codebooks.

Block-codes with a very small number of codewords are Investigated for the two special binary memoryless channels, the binary symmetric channel (BSC) and the Z-channel (ZC). The optimal (In the sense of minimum average error probability, using maximum likelihood decoding) code structure Is derived for the cases of two, three, and four codewords and an arbitrary blocklength. It Is shown that for two possible messages, on a BSC, the so-called flip codes of type t are optimal for any t, while on a ZC, the flip code of type 0 is optimal. For codes with three or four messages It Is shown that the so-called weak flip codes of some given type are optimal where the type depends on the blocklength. For all cases an algorithm Is presented that constructs an optimal code for blocklength n recursively from an optimal code of length n - 1. For the ZC a recursive optimal code design Is conjectured In the case of live possible messages. The derivation of these optimal codes relies heavily on a new approach of constructing and analyzing the code-matrix not row-wise (codewords), but column-wise. Moreover, these results also prove that the minimum Hamming distance might be the wrong design criterion for optimal codes even for very symmetric channels like the BSC.