Search

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

This paper investigates reducing sub-packetization of capacity-achieving schemes for uncoded Storage Constrained Private Information Retrieval (SC-PIR) systems. In the SC-PIR system, a user aims to download one out of K files from N servers while revealing nothing about the identity of the requested file to any individual server, in which the K files are stored at the N servers in an uncoded form and each server can store up to μK equivalent files, where μ is the normalized storage capacity of each server. We first prove that there exists a capacity-achieving SC-PIR scheme for a given storage design if and only if all the packets are stored exactly at M ≜ μN servers for μ such that M = μN ∈ {2,3, . . . ,N}. Then, the optimal sub-packetization for capacity-achieving linear SC-PIR schemes is characterized as the solution to an optimization problem, which is typically hard to solve since it involves non-continuous indicator functions. Moreover, a new notion of array called Storage Design Array (SDA) is introduced for the SC-PIR system. With any given SDA, an associated capacity-achieving SC-PIR scheme is constructed. Next, the SC-PIR schemes that have equal-size packets are investigated. Furthermore, the optimal equal-size sub-packetization among all capacity-achieving linear SC-PIR schemes characterized by Woolsey et al. is proved to be N(M−1)/gcd (N,M), which is achieved by a construction of SDA. Finally, by allowing unequal size of packets, a greedy SDA construction is proposed, where the sub-packetization of the associated SC-PIR scheme is upper bounded by N(M−1)/gcd (N,M). Among all capacity-achieving linear SC-PIR schemes, the sub-packetization is optimal when min{M,N−M}|N or M = N, and within a multiplicative gap min{M,N−M}/gcd (N,M) of the optimal one in general. In particular, for the special case N = d ⋅ M ± 1 where the positive integer d ≥ 2, we propose another SDA construction to obtain lower sub-packetization. [ABSTRACT FROM AUTHOR]

The parameters of a q-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed. [ABSTRACT FROM AUTHOR]

The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across $N$ servers. There are up to $N - R$ stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than $2N$. Moreover, the optimal design parameters such as the partitioning of the input matrices are discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication. [ABSTRACT FROM AUTHOR]

We introduce two notions of discrepancy between binary vectors, which are not metric functions in general but nonetheless capture the mathematical structure of the binary asymmetric channel. These lead to two new fundamental parameters of binary error-correcting codes, both of which measure the probability that the maximum likelihood decoder fails. We then derive various bounds for the cardinality and weight distribution of a binary code in terms of these new parameters, giving examples of codes meeting the bounds with equality. [ABSTRACT FROM AUTHOR]

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads $N$ is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from $N$ distinct noisy reads. We focus on channels that introduce a single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of $N$. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant symbols required can be gracefully reduced from $\log _{q} n+O(1)$ to $\log _{q} \log _{q} n+O(1)$ , and then to $O(1)$ , where $n$ denotes the length of a codeword. We also show that these reconstruction codes are asymptotically optimal. Finally, via computer simulations, we demonstrate that in certain cases, reconstruction codes can achieve similar performance as classical error-correcting codes with less redundant symbols. [ABSTRACT FROM AUTHOR]

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min{1, 2(n−t)/n} for any 1 ≤ t < n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart. [ABSTRACT FROM AUTHOR]

The original coded caching scenario assumes a content library that is of interest to all receiving users. In a realistic scenario though, the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, 40% of the users and each user has potential interest in 40% of the library? In this work, we investigate the so- called symmetrically selfish coded caching scenario, where each user only makes requests from a subset of the library that defines its own file demand set (FDS), each user caches selfishly only contents from its own FDS, and where the different FDSs symmetrically overlap to some extent. In the context of various traditional prefetching scenarios (prior to the emergence of coded caching), selfish approaches were known to be potentially very effective. On the other hand — with the exception of some notable works — little is known about selfish coded caching. We here present a new information-theoretic converse that proves, in a general setting of symmetric FDS structures, that selfish coded caching, despite enjoying a much larger local caching gain and a much smaller set of possible demands, introduces an unbounded load increase compared to the unselfish case. In particular, in the $K$ -user broadcast channel where each user stores a fraction $\gamma $ of the library, where each file (class) is of interest to $\alpha $ users, and where any one specific file is of interest to a fraction $\delta $ of users, the optimal coding gain of symmetrically selfish caching is at least $(K - \alpha)\gamma + 1$ times smaller than in the unselfish scenario. This allows us to draw the powerful conclusion that the optimal selfish coding gain is upper bounded by $1/(1 - \delta)$ , and thus does not scale with $K$. These derived limits are shown to be exact for different types of demands. In the end, this work provides, in a unified manner, the strong conclusion that selfish caching can cause unbounded performance deterioration in coded caching systems. [ABSTRACT FROM AUTHOR]

Minimum energy required to achieve a distortion-noise profile, i.e., a function indicating the maximum allowed distortion value for each channel noise level, is studied for transmission of Gaussian sources over Gaussian channels. A general coding scheme is proposed to upper bound the minimum energy needed for any distortion-noise profile. Conversely, utilizing a family of lower bounds originally derived for broadcast channels with power constraints, the minimum required energy is lower bounded for any profile. As examples, linear, exponential, square-law, and staircase profiles are studied. It is shown that for the linear profile, as well as for any concave profile, uncoded transmission is optimal. As a negative result, it is shown that exponential profiles are not achievable with finite energy. For square-law and staircase profiles, upper bounds and lower bounds are derived and the gaps between them are studied. [ABSTRACT FROM AUTHOR]

We consider the task of communicating a generic bivariate function of two classical correlated sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. We first propose a coding scheme based on asymptotically good algebraic structured codes, in particular, nested coset codes, and provide a set of sufficient conditions for the reconstruction of the function of the sources over a CQ-MAC. The proposed technique enables the decoder to recover the desired function without recovering the sources themselves. We further improve this by employing a coding scheme based on a classical superposition of algebraic structured codes and unstructured codes. This coding scheme allows exploiting the symmetric structure common amongst the sources and also leverage the asymmetries. We derive a new set of sufficient conditions that strictly enlarges the largest known set of sources whose function can be reconstructed over any given CQ-MAC, and identify examples demonstrating the same. We provide these conditions in terms of single-letter quantum information-theoretic quantities. [ABSTRACT FROM AUTHOR]

Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length $|V|$ on $G$. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate. If $G$ contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate $> 1/2$ is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems. [ABSTRACT FROM AUTHOR]

Consider a user who wishes to store a file in multiple servers such that at least $t$ servers are needed to reconstruct the file, and $z$ colluding servers cannot learn any information about the file. Unlike traditional secret-sharing models, where perfectly secure channels are assumed to be available at no cost between the user and each server, we assume that the user can only send data to the servers via a public channel, and that the user and each server share an individual secret key with length $n$. For a given $n$ , we determine the maximal length of the file that the user can store, and thus quantify the necessary cost to store a file of a certain length, in terms of the length of the secret keys that the user needs to share with the servers. Additionally, for this maximal file length, we determine (i) the optimal amount of local randomness needed at the user, (ii) the optimal amount of public communication from the user to the servers, and (iii) the optimal amount of storage requirement at the servers. [ABSTRACT FROM AUTHOR]

An $(n,r,h,a,q)$ -Local Reconstruction Code (LRC) is a linear code over $\mathbb {F}_{q}$ of length $n$ , whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies ‘ $a$ ’ local parity checks to recover from ‘ $a$ ’ erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience—namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to ‘ $a$ ’ erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$ -MR LRCs with field size $q$ bounded by $\left ({O\left ({\max \{r,n/r\}}\right)}\right)^{\min \{h,r-a\}}$. This significantly improves upon known constructions in many practically relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=\Theta (\sqrt {n})$ , $r-a=\Theta (\sqrt {n})$ and $h$ is a fixed constant with $h \leqslant a+2$ , achieving the optimal field size of $\Theta _{h}(n^{h/2})$. Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory. [ABSTRACT FROM AUTHOR]

The DNA storage channel is considered, in which a codeword is comprised of $M$ unordered DNA molecules. At reading time, $N$ molecules are sampled with replacement, and then each molecule is sequenced. A coded-index concatenated-coding scheme is considered, in which the $m$ th molecule of the codeword is restricted to a subset of all possible molecules (an inner code), which is unique for each $m$. The decoder has low-complexity, and is based on first decoding each molecule separately (the inner code), and then decoding the sequence of molecules (an outer code). Only mild assumptions are made on the sequencing channel, in the form of the existence of an inner code and decoder with vanishing error. The error probability of a random code as well as an expurgated code is analyzed and shown to decay exponentially with $N$. This establishes the importance of increasing the coverage depth $N/M$ in order to obtain low error probability. [ABSTRACT FROM AUTHOR]

It is well known that independent (separate) encoding of $K$ correlated sources may incur some rate loss compared to joint encoding, even if the decoding is done jointly. This loss is particularly evident in the multiple descriptions problem, where it is the same source that is encoded in each description. We observe that under mild conditions about the source and distortion measure, the sum-rate of $K$ separately encoded individually good descriptions tends to the rate-distortion function of the joint decoder in the limit of vanishing small coding rates of the descriptions. Moreover, we then propose to successively encode the source into $K$ independent descriptions in each round in order to achieve a final distortion $D$ after $M$ rounds. We provide two examples – a Gaussian source with mean-squared error and an exponential source with one-sided error – for which the excess rate vanishes in the limit as the number of rounds $M$ goes to infinity, for any fixed $D$ and $K$. This result has an interesting interpretation for a multi-round variant of the multiple descriptions problem, where after each round the encoder gets a (block) feedback regarding which of the descriptions arrived: In the limit as the number of rounds $M$ goes to infinity (i.e., many incremental rounds), the total rate of received descriptions approaches the rate-distortion function. We provide theoretical and experimental evidence showing that this phenomenon is in fact more general than in the two examples above. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the mean of a symmetric log-concave distribution under the constraint that only a single bit per sample from this distribution is available to the estimator. We study the mean squared error as a function of the sample size (and hence the number of bits). We consider three settings: first, a centralized setting, where an encoder may release $n$ bits given a sample of size $n$ , and for which there is no asymptotic penalty for quantization; second, an adaptive setting in which each bit is a function of the current observation and previously recorded bits, where we show that the optimal relative efficiency compared to the sample mean is precisely the efficiency of the median; lastly, we show that in a distributed setting where each bit is only a function of a local sample, no estimator can achieve optimal efficiency uniformly over the parameter space. We additionally complement our results in the adaptive setting by showing that one round of adaptivity is sufficient to achieve optimal mean-square error. [ABSTRACT FROM AUTHOR]

We propose a new method to compute the feedback capacity of unifilar finite state channels (FSCs) with memory using reinforcement learning (RL). The feedback capacity was previously estimated using its formulation as a Markov decision process (MDP) with dynamic programming (DP) algorithms. However, their computational complexity grows exponentially with the channel alphabet size. Therefore, we use RL, and specifically, its ability to parameterize value functions and policies with neural networks, to evaluate numerically the feedback capacity of channels with a large alphabet size. The outcome of the RL algorithm is a numerical lower bound on the feedback capacity, which is used to reveal the structure of the optimal solution. The structure is modeled by a graph-based auxiliary random variable that is utilized to derive an analytic upper bound on the feedback capacity with the duality bound. The capacity computation is concluded by verifying the tightness of the upper bound by testing whether it is Bahl-Cocke-Jelinek-Raviv (BCJR) invariant. We demonstrate this method on the Ising channel with an arbitrary alphabet size. For an alphabet size smaller than or equal to 8, we derive the analytic solution of the capacity. Next, the structure of the numerical solution is used to deduce a simple coding scheme that achieves the feedback capacity and serves as a lower bound for larger alphabets. For an alphabet size greater than 8, we present an upper bound on the feedback capacity. For an asymptotically large alphabet size, we present an asymptotic optimal coding scheme. [ABSTRACT FROM AUTHOR]

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2\log (n)$ bits in one sub-regime, and at most $\Omega ({n})$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping. [ABSTRACT FROM AUTHOR]

We consider finite-state channels (FSCs) where the channel state is stochastically dependent on the previous channel output. We refer to these as Noisy Output is the STate (NOST) channels. We derive the feedback capacity of NOST channels in two scenarios: with and without causal state information (CSI) available at the encoder. If CSI is unavailable, the feedback capacity is $C_{\text {FB}}= \max _{P(x|y')} I(X;Y|Y')$ , while if it is available at the encoder, the feedback capacity is $C_{\text {FB-CSI}}= \max _{P(u|y'),x(u,s')} I(U;Y|Y')$ , where $U$ is an auxiliary RV with finite cardinality. In both formulas, the output process is a Markov process with stationary distribution. The derived formulas generalize special known instances from the literature, such as where the state is i.i.d. and where it is a deterministic function of the output. $C_{\text {FB}}$ and $C_{\text {FB-CSI}}$ are also shown to be computable via convex optimization problem formulations. Finally, we present an example of an interesting NOST channel for which CSI available at the encoder does not increase the feedback capacity. [ABSTRACT FROM AUTHOR]

We consider the problem of covert communication over a state-dependent channel when the Channel State Information (CSI) is available either non-causally, causally, or strictly causally, either at the transmitter alone, or at both transmitter and receiver. Covert communication with respect to an adversary, called “warden,” is one in which, despite communication over the channel, the warden’s observation remains indistinguishable from an output induced by innocent channel-input symbols. Covert communication involves fooling an adversary in part by a proliferation of codebooks; for reliable decoding at the legitimate receiver, the codebook uncertainty is typically removed via a shared secret key that is unavailable to the warden. In contrast to previous work, we do not assume the availability of a large shared key at the transmitter and legitimate receiver. Instead, we only require a secret key with negligible rate to bootstrap the communication and our scheme extracts shared randomness from the CSI in a manner that keeps it secret from the warden, despite the influence of the CSI on the warden’s output. When CSI is available at the transmitter and receiver, we derive the covert capacity region. When CSI is only available at the transmitter, we derive inner and outer bounds on the covert capacity. We also provide examples for which the covert capacity is positive with knowledge of CSI but is zero without it. [ABSTRACT FROM AUTHOR]

We consider a transmitter and $K$ receivers, each of which shares a key variable with the transmitter. Through a noiseless broadcast channel, the transmitter wishes to send a common message $W$ securely to $N$ out of the $K$ receivers while the remaining $K-N$ receivers learn no information about $W$. We are interested in the maximum message rate, i.e., the maximum number of bits of $W$ that can be securely groupcast to the legitimate receivers per key block and the minimum broadcast bandwidth, i.e., the minimum number of bits of the broadcast information required to securely groupcast the message bits. We focus on the setting of combinatorial keys, where every subset of the $K$ receivers share an independent key of arbitrary size. Under this combinatorial key setting, the maximum message rate is characterized for the following scenarios - 1) $N=1$ or $N=K-1$ , i.e., secure unicast to 1 receiver with $K-1$ eavesdroppers or secure groupcast to $K-1$ receivers with 1 eavesdropper, 2) $N=2, K=4$ , i.e., secure groupcast to 2 out of 4 receivers, and 3) the symmetric setting where the key size for any subset of the same cardinality is equal for any $N,K$. Further, for the latter two cases, the minimum broadcast bandwidth for the maximum message rate is characterized. [ABSTRACT FROM AUTHOR]

Interactive coding allows two or more parties to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work (the second part) we provide computationally efficient, constant rate schemes that conduct any computation on arbitrary networks, and succeed with high probability in the presence of adversarial noise that can insert, delete, or alter communicated messages. Our schemes are non-fully-utilized and incur a polynomial (in the size of the network) blowup in the round complexity. Our first scheme resists an oblivious adversary that corrupts at most a fraction $\frac { \varepsilon }{m}$ of the total communication, where $m$ is the number of links in the network and $\varepsilon $ is a small constant. In contrast to the first part of this work, the scheme in this part does not assume that the parties pre-share a long random string. Our second scheme resists an arbitrary (non-oblivious) adversary that corrupts at most a fraction $\frac { \varepsilon }{m\log m}$ of the communication. We further improve the resilience to $\vphantom {\sum ^{R}}\frac { \varepsilon }{m\log \log m}$ by assuming the parties pre-share a long common random $\vphantom {\sum ^{R}}$ string. [ABSTRACT FROM AUTHOR]

We study the relation between latency and alphabet size in the context of Multicast Network Coding. Given a graph $G = (V, E)$ representing a communication network, a subset $S \subseteq V$ of sources, each of which initially holds a set of information messages, and a set $T \subseteq V$ of terminals; we consider the problem in which one wishes to design a communication scheme that eventually allows all terminals to obtain all the messages held by the sources. In this study we assume that communication is performed in rounds, where in each round each network node may transmit a single (possibly encoded) information packet on any of its outgoing edges. The objective is to minimize the communication latency, i.e., number of communication rounds needed until all terminals have all the messages of the source nodes. For sufficiently large alphabet sizes (i.e., large block length, packet sizes), it is known that traditional linear multicast network coding techniques (such as random linear network coding) minimize latency. In this work we seek to study the task of minimizing latency in the setting of limited alphabet sizes (i.e., finite block length), and alternatively, the task of minimizing the alphabet size in the setting of bounded latency. We focus on the establishing the computation complexity of the problem and present several intractability results. In particular, through reductive arguments, we prove that it is NP-hard to (i) approximate (and in particular to determine) the minimum alphabet size given a latency constraint; (ii) approximate (and in particular to determine) the minimum latency of communication schemes in the setting of limited alphabet sizes. [ABSTRACT FROM AUTHOR]

We consider the problem of secure distributed matrix computation (SDMC), where a user queries a function of data matrices generated at distributed source nodes. We assume the availability of $N$ honest but curious computation servers, which are connected to the sources, the user, and each other through orthogonal and reliable communication links. Our goal is to minimize the amount of data that must be transmitted from the sources to the servers, called the upload cost, while guaranteeing that no $T$ colluding servers can learn any information about the source matrices, and the user cannot learn any information beyond the computation result. We first focus on secure distributed matrix multiplication (SDMM), considering two matrices, and propose a novel polynomial coding scheme using the properties of finite field discrete Fourier transform, which achieves an upload cost significantly lower than the existing results in the literature. We then generalize the proposed scheme to include straggler mitigation, and to the multiplication of multiple matrices while keeping the input matrices, the intermediate computation results, as well as the final result secure against any $T$ colluding servers. We also consider a special case, called computation with own data, where the data matrices used for computation belong to the user. In this case, we drop the security requirement against the user, and show that the proposed scheme achieves the minimal upload cost. We then propose methods for performing other common matrix computations securely on distributed servers, including changing the parameters of secret sharing, matrix transpose, matrix exponentiation, solving a linear system, and matrix inversion, which are then used to show how arbitrary matrix polynomials can be computed securely on distributed servers using the proposed procedure. [ABSTRACT FROM AUTHOR]

We introduce and analyse the problem of encoding classical information into different resources of a quantum state. More precisely, we consider a general class of communication scenarios characterised by encoding operations that commute with a unique resource destroying map and leave free states invariant. Our motivating example is given by encoding information into coherences of a quantum system with respect to a fixed basis (with unitaries diagonal in that basis as encodings and the decoherence channel as a resource destroying map), but the generality of the framework allows us to explore applications ranging from super-dense coding to thermodynamics. For any state, we find that the number of messages that can be encoded into it using such operations in a one-shot scenario is upper bounded in terms of the information spectrum relative entropy between the given state and its version with erased resources. Furthermore, if the resource destroying map is the twirling channel over some unitary group, we find matching one-shot lower bounds as well. In the asymptotic setting where we encode into many copies of the resource state, our bounds yield an operational interpretation of resource monotones such as the relative entropy of coherence and its corresponding relative entropy variance. [ABSTRACT FROM AUTHOR]

Distributed matrix computations over large clusters can suffer from the problem of slow or failed worker nodes (called stragglers) which can dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running “coded” copies of tasks comprising a job; stragglers are typically treated as erasures. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Several practical matrix computation scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity. This is problematic as it results in significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. Furthermore, some MDS techniques also suffer from significant numerical stability issues. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments on Amazon Web Services (AWS) clusters support our findings. [ABSTRACT FROM AUTHOR]

We consider the setting of a distributed storage system where a single file is subdivided into smaller fragments of same size which are then replicated with a common replication factor across servers of identical cache size. An incoming file download request is sent to all the servers, and the download is completed whenever the request gathers all the fragments. At each server, we are interested in determining the set of fragments to be stored, and the sequence in which fragments should be accessed, such that the mean file download time for a request is minimized. We model the fragment download time as an exponential random variable independent and identically distributed for all fragments across all servers, and show that the mean file download time can be lower bounded in terms of the expected number of useful servers summed over all distinct fragment downloads. We present deterministic storage schemes that attempt to maximize the number of useful servers. We show that finding the optimal sequence of accessing the fragments is a Markov decision problem, whose complexity grows exponentially with the number of fragments. We propose heuristic algorithms that determine the sequence of access to the fragments which are empirically shown to perform well. [ABSTRACT FROM AUTHOR]

We show that the problem of code construction for multiple access channel (MAC) resolvability can be reduced to the simpler problem of code construction for source resolvability. Specifically, we propose a MAC resolvability code construction that relies on a combination of multiple source resolvability codes, used in a black-box manner, and leverages randomness recycling implemented via distributed hashing and block-Markov coding. Since explicit source resolvability codes are known, our results also yield the first explicit coding schemes that achieve the entire MAC resolvability region for any discrete memoryless multiple-access channel with binary input alphabets. [ABSTRACT FROM AUTHOR]

We consider the coded caching problem with an additional privacy constraint that a user should not get any information about the demands of the other users. We first show that a demand-private scheme for $N$ files and $K$ users can be obtained from a non-private scheme that serves only a subset of the demands for the $N$ files and $NK$ users problem. We further use this fact to construct a demand-private scheme for $N$ files and $K$ users from a particular known non-private scheme for $N$ files and $NK-K+1$ users. It is then demonstrated that, the memory-rate pair $(M,\min \{N,K\}(1-M/N))$ , which is achievable for non-private schemes with uncoded transmissions, is also achievable under demand privacy. We further propose a scheme that improves on these ideas by removing some redundant transmissions. The memory-rate trade-off achieved using our schemes is shown to be within a multiplicative factor of 3 from the optimal when $K < N$ and of 8 when $N \leq K$. Finally, we give the exact memory-rate trade-off for demand-private coded caching problems with $N\geq K=2$. [ABSTRACT FROM AUTHOR]

We show that a relatively simple reasoning using von Neumann entropy inequalities yields a robust proof of the quantum Singleton bound for quantum error-correcting codes (QECC). For entanglement-assisted quantum error-correcting codes (EAQECC) and catalytic codes (CQECC), a type of generalized quantum Singleton bound [Brun et al., IEEE Trans. Inf. Theory 60(6):3073–3089 (2014)] was believed to hold for many years until recently one of us found a counterexample [MG, Phys. Rev. A 103, 020601 (2021)]. Here, we rectify this state of affairs by proving the correct generalized quantum Singleton bound, extending the above-mentioned proof method for QECC; we also prove information-theoretically tight bounds on the entanglement-communication tradeoff for EAQECC. All of the bounds relate block length $n$ and code length $k$ for given minimum distance $d$ and we show that they are robust, in the sense that they hold with small perturbations for codes which only correct most of the erasure errors of less than $d$ letters. In contrast to the classical case, the bounds take on qualitatively different forms depending on whether the minimum distance is smaller or larger than half the block length. We also provide a propagation rule: any pure QECC yields an EAQECC with the same distance and dimension, but of shorter block length. [ABSTRACT FROM AUTHOR]

Optimal zero-delay coding (quantization) of $\mathbb {R}^{d}$ -valued linearly generated Markov sources is studied under quadratic distortion. The structure and existence of deterministic and stationary coding policies that are optimal for the infinite horizon average cost (distortion) problem are established. Prior results studying the optimality of zero-delay codes for Markov sources for infinite horizons either considered finite alphabet sources or, for the $\mathbb {R}^{d}$ -valued case, only showed the existence of deterministic and non-stationary Markov coding policies or those which are randomized. In addition to existence results, for finite blocklength (horizon) $T$ the performance of an optimal coding policy is shown to approach the infinite time horizon optimum at a rate $O\left({\frac {1}{T}}\right)$. This gives an explicit rate of convergence that quantifies the near-optimality of finite window (finite-memory) codes among all optimal zero-delay codes. [ABSTRACT FROM AUTHOR]

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon >0$ , we give an algebraic construction of an infinite family of error-correcting codes of rate $R$ , over an alphabet of size $(1/\epsilon)^{O(1/\epsilon ^{2})}$ , that can be list decoded from a $(1-R-\epsilon)$ -fraction of errors with list size at most $\exp (\mathrm {poly}(1/ \epsilon))$. Moreover, the codes can be encoded in time $\mathrm {poly}(1/ \epsilon,n)$ , the output list is contained in a linear subspace of dimension at most $\mathrm {poly}(1/ \epsilon)$ , and a basis for this subspace can be found in time $\mathrm {poly}(1 /\epsilon, n)$. Thus, both encoding and list decoding can be performed in fully polynomial-time $\mathrm {poly}(1/ \epsilon,n)$ , except for pruning the subspace and outputting the final list which takes time $\exp (\mathrm {poly}(1/ \epsilon)) \cdot \mathrm {poly} (n)$. In contrast, prior explicit and efficient constructions of capacity-achieving list decodable codes either required a much higher complexity in terms of $1/ \epsilon $ (and were additionally much less structured), or had super-constant alphabet or list sizes. Our codes are quite natural and structured. Specifically, we use algebraic-geometric (AG) codes with evaluation points restricted to a subfield, and with the message space restricted to a (carefully chosen) linear subspace. Our main observation is that the output list of AG codes with subfield evaluation points is contained in an affine shift of the image of a block-triangular-Toeplitz (BTT) matrix, and that the list size can potentially be reduced to a constant by restricting the message space to a BTT evasive subspace, which is a large subspace that intersects the image of any BTT matrix in a constant number of points. We further show how to explicitly construct such BTT evasive subspaces, based on the explicit subspace designs of Guruswami and Kopparty (Combinatorica, 2016), and composition. [ABSTRACT FROM AUTHOR]

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems. In this work, in order to reduce the wear out of the cells, we propose a new coding scheme, called endurance-limited memories (ELM) codes, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an $\ell $ -change $t$ -write ELM code is a coding scheme that allows to write $t$ messages into some $n$ binary cells while guaranteeing that each cell is programmed at most $\ell $ times. In case $\ell =1$ , these codes coincide with the well-studied write-once memory (WOM) codes. We study some models of these codes which depend upon whether the encoder knows on each write the number of times each cell was programmed, knows only the memory state, or even does not know anything. For the decoder, we consider these similar three cases. We fully characterize the capacity regions and the maximum sum-rates of three models where the encoder knows on each write the number of times each cell was programmed. In particular, it is shown that in these models the maximum sum-rate is $\log \sum _{i=0}^{\ell } {\binom{t }{ i}}$. We also study and expose the capacity regions of the models where the decoder is informed with the number of times each cell was programmed. Finally we present the most practical model where the encoder read the memory before encoding new data and the decoder has no information about the previous states of the memory. [ABSTRACT FROM AUTHOR]

A novel fault-tolerant computation technique based on array Belief Propagation (BP)-decodable XOR (BP-XOR) codes is proposed for distributed matrix-matrix multiplication. The proposed scheme is shown to be configurable and suited for modern hierarchical compute architectures such as Graphical Processing Units (GPUs) equipped with multiple nodes, whereby each has many small independent processing units with increased core-to-core communications. The proposed scheme is shown to outperform a few of the well–known earlier strategies in terms of total end-to-end execution time while in presence of slow nodes, called stragglers. This performance advantage is due to the careful design of array codes which distributes the encoding operation over the cluster (slave) nodes at the expense of increased master-slave communication. An interesting trade-off between end-to-end latency and total communication cost is precisely described. In addition, to be able to address an identified problem of scaling stragglers, an asymptotic version of array BP-XOR codes based on projection geometry is proposed at the expense of some computation overhead. A thorough latency analysis is conducted for all schemes to demonstrate that the proposed scheme achieves order-optimal computation in both the sublinear as well as the linear regimes in the size of the computed product from an end-to-end delay perspective. [ABSTRACT FROM AUTHOR]

We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when requests arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by Rawat et al. are asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or equal to 4, respectively larger or equal to 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove a hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erdős and Sós. We then apply the constructions and bounds by Erdős, Frankl and Rödl about this generalization of the (6,3)-problem, known as the ($3\varrho $ -3, $\varrho $)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. We derive bounds on the optimal redundancy of several families of asynchronous batch codes with the query size $t=2$. In particular, we show that the optimal redundancy $\rho (k)$ of graph-based asynchronous batch codes of dimension $k$ for $t=2$ is $2\sqrt {k}$. Moreover, for graph-based asynchronous batch codes with $t \ge 3$ , $\rho (k) = O\left ({{k}^{1/(2-\epsilon)}}\right)$ for any small $\epsilon >0$. [ABSTRACT FROM AUTHOR]

We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures that make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this the private index coding problem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where the server has the ability to multicast to any subset of users, and demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required. [ABSTRACT FROM AUTHOR]

We consider the problem of (almost) lossless separate encodings and joint decoding of two correlated discrete memoryless sources (DMSs), that is, the well-known Slepian-Wolf (S-W) source coding problem. Traditionally, ensembles of S–W codes are defined such that every bin of each $n$ –vector of each source is randomly drawn under the uniform distribution across the sets $\{0,1,\ldots,2^{nR_{X}}-1\}$ and $\{0,1,\ldots,2^{nR_{Y}}-1\}$ , where $R_{X}$ and $R_{Y}$ are the coding rates of the two sources, $X$ and $Y$ , respectively. In a few more recent works, where only one source, say, $X$ , is compressed and the other one, $Y$ , serves as side information available at the decoder, the scope is extended to variable–rate S–W (VRSW) codes, where the rate is allowed to depend on the type class of the source string, but still, the random–binning distribution is assumed uniform within the corresponding, type–dependent, bin index set. In this expository work, we investigate the role of the uniformity of the random binning distribution from the perspective of the trade-off between the reliability (defined in terms of the error exponent) and the compression performance (measured from the viewpoint of the source coding exponent). To this end, we study a much wider class of random–binning distributions, which includes the ensemble of VRSW codes as a special case, but it also goes considerably beyond. We first show that, with the exception of some pathological cases, the smaller ensemble, of VRSW codes, is as good as the larger ensemble in terms the trade-off between the error exponent and the source coding exponent. Notwithstanding this finding, the wider class of ensembles proposed is motivated in two ways. The first is that it outperforms VRSW codes in the above–mentioned pathological cases, and the second is that it allows robustness: in the event of a system failure that causes unavailability of the compressed bit–stream from one of the sources, it still allows reconstruction of the other source within some controllable distortion. [ABSTRACT FROM AUTHOR]

It is known that continuous variable quantum information cannot be protected against naturally occurring noise using Gaussian states and operations only. Noh et al. proposed bosonic oscillator-to-oscillator codes relying on non-Gaussian resource states as an alternative, and showed that these encodings can lead to a reduction of the effective error strength at the logical level as measured by the variance of the classical displacement noise channel. An oscillator-to-oscillator code embeds K logical bosonic modes (in an arbitrary state) into N physical modes by means of a Gaussian N-mode unitary and N-K auxiliary one-mode Gottesman-Kitaev-Preskill-states. Here we ask if – in analogy to qubit error-correcting codes – there are families of oscillator-to-oscillator codes with the following threshold property: They allow to convert physical displacement noise with variance below some threshold value to logical noise with variance upper bounded by any (arbitrary) constant. We find that this is not the case if encoding unitaries involving a constant amount of squeezing and maximum likelihood error decoding are used. We show a general lower bound on the logical error probability which is only a function of the amount of squeezing and independent of the number of modes. As a consequence, any physically implementable family of oscillator-to-oscillator codes combined with maximum likelihood error decoding does not admit a threshold. [ABSTRACT FROM AUTHOR]

Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study these three algorithms (PA, EC, and DC) in the presence of quantum side information, and show that they all become equivalent in the one-shot scenario. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD. [ABSTRACT FROM AUTHOR]

We construct and analyze a family of low-density parity check (LDPC) quantum codes with a linear encoding rate, distance scaling as $n^\epsilon $ for $\epsilon > 0$ and efficient decoding schemes. The code family is based on tessellations of closed, four-dimensional, hyperbolic manifolds, as first suggested by Guth and Lubotzky. The main contribution of this work is the construction of suitable manifolds via finite presentations of Coxeter groups, their linear representations over Galois fields and topological coverings. We establish a lower bound on the encoding rate $k/n$ of $13/72 = 0.180\ldots $ and we show that the bound is tight for the examples that we construct. Numerical simulations give evidence that parallelizable decoding schemes of low computational complexity suffice to obtain high performance. These decoding schemes can deal with syndrome noise, so that parity check measurements do not have to be repeated to decode. Our data is consistent with a threshold of around 4% in the phenomenological noise model with syndrome noise in the single-shot regime. [ABSTRACT FROM AUTHOR]

We study the adjacency graphs of feedback shift registers (FSRs) with affine characteristic functions. We first show that, similar to the linear case, the output sequences of FSRs with affine characteristic functions also have the direct sum decompositions. The only difference from the linear case is that one component of the decomposition is a family of affine sequences, rather than linear sequences. Then, based on this fact, we give a relationship between the adjacency graphs of FSRs with affine characteristic functions and the generalized adjacency graphs of FSRs whose characteristic functions correspond to the components of the decomposition. This relationship establishes the algebraic structure of adjacency graphs and greatly simplifies the calculation of them. At last, we especially study the adjacency graph of the FSR whose characteristic function is $q_{k}(x)+1$ where $q_{k}(x)$ is the linear function corresponding to the polynomial $(1+x)^{k}$. We prove that for any two cycles of this FSR, the number of conjugate pairs shared by them is no more than 4 if $k$ is a power of 2, and no more than 2 if $k$ is not a power of 2. [ABSTRACT FROM AUTHOR]

Error-correcting codes over sets, with applications to DNA storage, are studied. The DNA-storage channel receives a set of sequences, and produces a corrupted version of the set, including sequence loss, symbol substitution, symbol insertion/deletion, and limited-magnitude errors in symbols. Various parameter regimes are studied. New bounds on code parameters are provided, which improve upon known bounds. New codes are constructed, at times matching the bounds up to lower-order terms or small constant factors. [ABSTRACT FROM AUTHOR]

Several applications in communication, control, and learning require approximating target distributions to within small informational divergence. The additional requirement of invertibility usually leads to using encoders that are one-to-one mappings, also known as distribution matchers. However, even the best one-to-one encoders have divergences that grow logarithmically with the block length. To overcome this limitation, an encoder is proposed that has an invertible one-to-many mapping and a low-rate random number generator (RNG). Two algorithms are developed to design the mapping by assigning strings in either a most-likely first or least-likely first order. Both algorithms give information rates approaching the entropy of the target distribution with exponentially decreasing divergence and with vanishing RNG rate in the block length. [ABSTRACT FROM AUTHOR]

We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by $q$ -ary list-decodable codes with non-vanishing information rate?” This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best-known result was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family. For any desired $\varepsilon > 0$ , we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma $ fraction of insertions and $\delta $ fraction of deletions as long as $\gamma + 2\delta \leq 1 - \varepsilon $. On the other hand, for any $\gamma, \delta $ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions. We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$ -piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve. The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of $\delta,\gamma $ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh and Ma, 2014]. Finally, we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate. [ABSTRACT FROM AUTHOR]

The subblock energy-constrained codes (SECCs) and sliding window-constrained codes (SWCCs) have recently attracted attention due to various applications in communication systems such as simultaneous energy and information transfer. In a SECC, each codeword is divided into smaller non-overlapping windows, called subblocks, and every subblock is constrained to carry sufficient energy. In a SWCC, however, the energy constraint is enforced over every window. In this work, we focus on the binary channel, where sufficient energy is achieved theoretically by using relatively high weight codes, and study the bounded SECCs and bounded SWCCs, where the weight in every window is bounded between a minimum and maximum number. Particularly, we focus on the cases of parameters that there is no rate loss, i.e. the channel capacity is one, and propose two methods to construct capacity-approaching codes with low redundancy and linear-time complexity, based on Knuth’s balancing technique and sequence replacement technique. These methods can be further extended to construct SECCs and SWCCs. For certain codes parameters, our methods incur only one redundant bit. We also impose the minimum distance constraint for error correction capability of the designed codes, which helps to reduce the error propagation during decoding as well. [ABSTRACT FROM AUTHOR]

This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability. [ABSTRACT FROM AUTHOR]

Exponential error bounds achievable by universal coding and decoding are derived for frame-asynchronous discrete memoryless multiple access channels with two senders, via the method of subtypes, a refinement of the method of types. An empirical entropy decoder is employed. A key tool is an improved packing lemma, that overcomes the technical difficulty caused by codeword repetitions via an induction based new argument. The asymptotic form of the bounds admits numerical evaluation. This demonstrates that error exponents achievable by synchronous transmission can be superseded via controlled asynchronism, i.e. a deliberate shift of the codewords. [ABSTRACT FROM AUTHOR]

In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems can be interpreted as gossip algorithms when applied to special systems encoding the underlying network and explain in detail their decentralized nature. Our general framework recovers a comprehensive array of well-known gossip algorithms as special cases, including the pairwise randomized gossip algorithm and path averaging gossip, and allows for the development of provably faster variants. The flexibility of the new approach enables the design of a number of new specific gossip methods. For instance, we propose and analyze novel block and the first provably accelerated randomized gossip protocols, and dual randomized gossip algorithms. From a numerical analysis viewpoint, our work is the first that explores in depth the decentralized nature of randomized iterative methods for linear systems and proposes them as methods for solving the average consensus problem. We evaluate the performance of the proposed gossip protocols by performing extensive experimental testing on typical wireless network topologies. [ABSTRACT FROM AUTHOR]

We present a new systematic approach to constructing spherical codes in dimensions $2^{k}$ , based on Hopf foliations. Using the fact that a sphere $S^{2n-1}$ is foliated by manifolds $S_{\cos \eta }^{n-1} \times S_{\sin \eta }^{n-1}$ , $\eta \in [0,\pi /2]$ , we distribute points in dimension $2^{k}$ via a recursive algorithm from a basic construction in $\mathbb {R}^{4}$. Our procedure outperforms some current constructive methods in several small-distance regimes and constitutes a compromise between achieving a large number of codewords for a minimum given distance and effective constructiveness with low encoding computational cost. Bounds for the asymptotic density are derived and compared with other constructions. The encoding process has storage complexity $O(n)$ and time complexity $O(n \log n)$. We also propose a sub-optimal decoding procedure, which does not require storing the codebook and has time complexity $O(n \log n)$. [ABSTRACT FROM AUTHOR]