# Information Theory (cs.IT)

• This paper introduces a class of specific puncturing patterns, called symmetric puncturing patterns, which can be characterized and generated from the rows of the generator matrix $G_N$. They are first shown to be non-equivalent, then a low-complexity method to generate symmetric puncturing patterns is proposed, which performs a search tree algorithm with limited depth, over the rows of $G_N$. Symmetric patterns are further optimized by density evolution, and shown to yield better performance than state-of-the-art rate compatible code constructions, relying on either puncturing or shortening techniques.
• This paper focuses on the recently introduced Successive Cancellation Flip (SCFlip) decoder of polar codes. Our contribution is twofold. First, we propose the use of an optimized metric to determine the flipping positions within the SCFlip decoder, which improves its ability to find the first error that occurred during the initial SC decoding attempt. We also show that the proposed metric allows closely approaching the performance of an ideal SCFlip decoder. Second, we introduce a generalisation of the SCFlip decoder to a number of $\omega$ nested flips, denoted by SCFlip-$\omega$, using a similar optimized metric to determine the positions of the nested flips. We show that the SCFlip-2 decoder yields significant gains in terms of decoding performance and competes with the performance of the CRC-aided SC-List decoder with list size L=4, while having an average decoding complexity similar to that of the standard SC decoding, at medium to high signal to noise ratio.
• We introduce a technique for the analysis of general spatially coupled systems that are governed by scalar recursions. Such systems can be expressed in variational form in terms of a potential functional. We show, under mild conditions, that the potential functional is \emphdisplacement convex and that the minimizers are given by the fixed points of the recursions. Furthermore, we give the conditions on the system such that the minimizing fixed point is unique up to translation along the spatial direction. The condition matches those in \citeKRU12 for the existence of spatial fixed points. \emphDisplacement convexity applies to a wide range of spatially coupled recursions appearing in coding theory, compressive sensing, random constraint satisfaction problems, as well as statistical mechanical models. We illustrate it with applications to Low-Density Parity-Check and generalized LDPC codes used for transmission on the binary erasure channel, or general binary memoryless symmetric channels within the Gaussian reciprocal channel approximation, as well as compressive sensing.
• To maximize offloading gain of cache-enabled device-to-device (D2D) communications, content placement and delivery should be jointly designed. In this letter, we jointly optimize caching and scheduling policies to maximize successful offloading probability, defined as the probability that a user can obtain desired file in local cache or via D2D link with data rate larger than a given threshold. We obtain the optimal scheduling factor for a random scheduling policy that can control interference in a distributed manner, and a low complexity solution to compute caching distribution. We show that the offloading gain can be remarkably improved by the joint optimization.
• We present a novel solution for Channel Assignment Problem (CAP) in Device-to-Device (D2D) wireless networks that takes into account the throughput estimation noise. CAP is known to be NP-hard in the literature and there is no practical optimal learning algorithm that takes into account the estimation noise. In this paper, we first formulate the CAP as a stochastic optimization problem to maximize the expected sum data rate. To capture the estimation noise, CAP is modeled as a noisy potential game, a novel notion we introduce in this paper. Then, we propose a distributed Binary Log-linear Learning Algorithm (BLLA) that converges to the optimal channel assignments. Convergence of BLLA is proved for bounded and unbounded noise. Proofs for fixed and decreasing temperature parameter of BLLA are provided. A sufficient number of estimation samples is given that guarantees the convergence to the optimal state. We assess the performance of BLLA by extensive simulations, which show that the sum data rate increases with the number of channels and users. Contrary to the better response algorithm, the proposed algorithm achieves the optimal channel assignments distributively even in presence of estimation noise.
• In this paper, we study a wireless packet broadcast system that uses linear network coding (LNC) to help receivers recover data packets that are missing due to packet erasures. We study two intertwined performance metrics, namely throughput and average packet decoding delay (APDD) and establish strong/weak approximation relations based on whether the approximation holds for the performance of every receiver (strong) or for the average performance across all receivers (weak). We prove an equivalence between strong throughput approximation and strong APDD approximation. We prove that throughput-optimal LNC techniques can strongly approximate APDD, and partition-based LNC techniques may weakly approximate throughput. We also prove that memoryless LNC techniques, including instantly decodable network coding techniques, are not strong throughput and APDD approximation nor weak throughput approximation techniques.
• For conventional secret sharing, if cheaters can submit possibly forged shares after observing shares of the honest users in the reconstruction phase then they cannot only disturb the protocol but also only they may reconstruct the true secret. To overcome the problem, secret sharing scheme with properties of cheater-identification have been proposed. Existing protocols for cheater-identifiable secret sharing assumed non-rushing cheaters or honest majority. In this paper, we remove both conditions simultaneously, and give its universal construction from any secret sharing scheme. To resolve this end, we propose the concepts of "individual identification" and "agreed identification".
• Two channels are said to be equivalent if they are degraded from each other. The space of equivalent channels with input alphabet $X$ and output alphabet $Y$ can be naturally endowed with the quotient of the Euclidean topology by the equivalence relation. A topology on the space of equivalent channels with fixed input alphabet $X$ and arbitrary but finite output alphabet is said to be natural if and only if it induces the quotient topology on the subspaces of equivalent channels sharing the same output alphabet. We show that every natural topology is $\sigma$-compact, separable and path-connected. On the other hand, if $|X|\geq 2$, a Hausdorff natural topology is not Baire and it is not locally compact anywhere. This implies that no natural topology can be completely metrized if $|X|\geq 2$. The finest natural topology, which we call the strong topology, is shown to be compactly generated, sequential and $T_4$. On the other hand, the strong topology is not first-countable anywhere, hence it is not metrizable. We show that in the strong topology, a subspace is compact if and only if it is rank-bounded and strongly-closed. We introduce a metric distance on the space of equivalent channels which compares the noise levels between channels. The induced metric topology, which we call the noisiness topology, is shown to be natural. We also study topologies that are inherited from the space of meta-probability measures by identifying channels with their posterior meta-probability distributions. We show that the weak-* topology is exactly the same as the noisiness topology and hence it is natural. We prove that if $|X|\geq 2$, the total variation topology is not natural nor Baire, hence it is not completely metrizable. Moreover, it is not locally compact anywhere. Finally, we show that the Borel $\sigma$-algebra is the same for all Hausdorff natural topologies.
• We study the continuity of many channel parameters and operations under various topologies on the space of equivalent discrete memoryless channels (DMC). We show that mutual information, channel capacity, Bhattacharyya parameter, probability of error of a fixed code, and optimal probability of error for a given code rate and blocklength, are continuous under various DMC topologies. We also show that channel operations such as sums, products, interpolations, and Arıkan-style transformations are continuous.
• Deduplication finds and removes long-range data duplicates. It is commonly used in cloud and enterprise server settings and has been successfully applied to primary, backup, and archival storage. Despite its practical importance as a source-coding technique, its analysis from the point of view of information theory is missing. This paper provides such an information-theoretic analysis of data deduplication. It introduces a new source model adapted to the deduplication setting. It formalizes both fixed and variable-length deduplication schemes, and it introduces a novel, multi-chunk deduplication scheme. It then provides an analysis of these three deduplication variants, emphasizing the importance of boundary synchronization between source blocks and deduplication chunks. In particular, under fairly mild assumptions, the proposed multi-chunk deduplication scheme is shown to be order optimal.
• Bitcoin and other cryptocurrencies have surged in popularity over the last decade. Although Bitcoin does not claim to provide anonymity for its users, it enjoys a public perception of being a `privacy-preserving' financial system. In reality, cryptocurrencies publish users' entire transaction histories in plaintext, albeit under a pseudonym; this is required for transaction validation. Therefore, if a user's pseudonym can be linked to their human identity, the privacy fallout can be significant. Recently, researchers have demonstrated deanonymization attacks that exploit weaknesses in the Bitcoin network's peer-to-peer (P2P) networking protocols. In particular, the P2P network currently forwards content in a structured way that allows observers to deanonymize users. In this work, we redesign the P2P network from first principles with the goal of providing strong, provable anonymity guarantees. We propose a simple networking policy called Dandelion, which achieves nearly-optimal anonymity guarantees at minimal cost to the network's utility. We also provide a practical implementation of Dandelion.
• The problem of operating a Gaussian Half-Duplex (HD) relay network optimally is challenging due to the exponential number of listen/transmit network states that need to be considered. Recent results have shown that, for the class of Gaussian HD networks with $N$ relays, there always exists a $simple$ schedule, i.e., with at most $N+1$ active states, that is sufficient for approximate (i.e., up to a constant gap) capacity characterization. This paper investigates how to efficiently find such a simple schedule over line networks. Towards this end, a polynomial-time algorithm is designed and proved to output a simple schedule that achieves the approximate capacity. The key ingredient of the algorithm is to leverage similarities between network states in HD and edge coloring in a graph. It is also shown that the algorithm allows to derive a closed-form expression for the approximate capacity of the Gaussian line network that can be evaluated distributively and in linear time.

### Recent comments

Samad Khabbazi Oskouei Sep 05 2016 11:34 UTC

I think that we have missed the "semi-" at the conclusion. Because, the proof of the theorem 4.3 is based on the using universal semi-density matrix concept which is not computable. The semi-computability concept used here is like the Kolmogorov complexity which is not computable and so the Cubic co

...(continued)
Toby Cubitt Sep 01 2016 11:14 UTC

I could well be missing something. But as far as I could tell from a rather quick read through the paper, all they show is that the quantum capacity of a channel with computable matrix elements is given by the regularised coherent information optimised over input ensembles with computable matrix ele

...(continued)
Māris Ozols Aug 30 2016 17:52 UTC

Do I understand correctly that this paper claims to show that quantum capacity is computable?

> After defining the algorithmic quantum capacity we have proved that it
> equals the standard one. Furthermore we have shown that it is
> computable.

Richard Kueng Jul 28 2015 07:01 UTC

fyi: our quantum implications are presented in Subsection 2.2 (pp 7-9).

Marco Tomamichel May 31 2015 22:07 UTC

Thanks for the comment! This is a good idea, I will do that in the next arXiv version.

Patrick Hayden May 28 2015 17:31 UTC

Wonderful! I've been waiting for a book like this for a while now! Thanks, Marco.

I do have one trivial comment from a 30 second preliminary scan, though: please consider typesetting the proofs with a font size matching the main text. If us readers are already squinting hard trying to understand

...(continued)
Marco Tomamichel Apr 02 2015 03:21 UTC

This is a preliminary version and I am happy to incorporate feedback I receive in the coming month. Any comments are welcome.

Māris Ozols Mar 17 2015 11:00 UTC

The strange equation is supposed to look like this:
$$f(\sqrt{a} X + \sqrt{1-a} Y) \geq a f(X) + (1-a) f(Y) \quad \forall a \in [0,1]$$

Yuanzhu Aug 02 2014 04:21 UTC

This algorithm is from Wu's list decoding algorithm.