Search

This paper proposes an enhanced Fully Informed Communication-Induced Checkpointing (FI-CIC) protocol to highly improve the possibility of detecting Z-cycle free patterns with no extra control message by utilizing the advantageous feature of the broadcast network in an effective way compared with the original FI-CIC protocol. Experimental results show that our protocol outperforms the previous one in terms of the number of forced checkpoints per process. [ABSTRACT FROM AUTHOR]

In recent years, it has been witnessed a boom in the development of mobile networks and a great increase in the computing ability of mobile devices. The rapid booming in client requests lead to some new challenges for real-time on-demand data broadcasting: (1) the dynamic diversity of the data characteristics; (2) the dynamic diversity of real-time clients' demand greatly increase the volume of hot-spot data (the most access data); and (3) the clients' demands for high service quality. To date, the current research has focused on the fixed-channel models (i.e. the bandwidth and number of channels are unchangeable) and algorithms. To adapt to the characteristics of the real-time requests, an optimized channel split method (OCSM) is proposed for automatic channel split and data allocation in this paper. The experiments undertaken in this study included two aspects: (1) determining the different strategies under different data sizes and deadlines; and (2) verifying the validity of the automatic channel split and data allocation through a series of experiments with the general performance matrics. The results show that the proposed method outperforms some of the state-of-the-art scheduling algorithms. [ABSTRACT FROM AUTHOR]

The most important application of vehicular networks is the dissemination of safety information via broadcasting protocols. How to reduce the redundant retransmission of the same information to avoid excessive channel collisions while ensure low latency and high reliability of the dissemination over the network has become the most challenging problem for multi-hop broadcasting protocols. The existing solutions use either probability-based multi-hop broadcasting for low latency or time-based deterministic approaches for high reliability. In this work, we propose a new probability-based multi-hop broadcast protocol to overcome the reliability and latency issues. First, we propose to assign a higher forwarding probability to the nodes that are farther from the source node by using a node's index number and other parameters, which is different from the existing probability-based approaches. The parameters can be adjusted for a higher forwarding success probability and maintain the required reliability of the message delivery. Second, we propose a clustering architecture so that redundancy and latency issues can be significantly reduced. Third, we analyze the protocol performance, such as the forwarding success probability, the average number of copies, and the average one-hop delay. The effectiveness of the proposed protocol has been demonstrated by extensive simulation results with significantly improved network performance. [ABSTRACT FROM AUTHOR]

Opportunistic routing is a promising technique that has been proposed for wireless mesh networks. It achieves significant performance gains under unstable wireless links since it can take advantage of the broadcast nature of the wireless medium. Many protocols of opportunistic routing have been proposed to increase transmission reliability and network throughput. Instead of using a dedicated next hop, opportunistic routing can consider multiple downstream nodes as potential forwarders. The decision of which nodes being chosen to forward packets is made by the coordination schema. Although the coordination helps opportunistic routing to deliver opportunistic gains, it requires a batch-based schedule to minimize the cost, which may prevent spatial channel reuse and thus under utilize wireless media. In this paper, we explain the fundamental idea of opportunistic routing and propose a discrete-time Markov chain as a general model to map the transmission process. It demonstrates how to map batch-based packet transmissions in the network with state transitions in a Markov chain. Our model considers the pipelined data transfer and evaluates opportunistic routing under different wireless networks in terms of the expected number of transmissions and time slots. It shows both the pros and cons of opportunistic routing and thus helps in the design of future protocols of opportunistic routing. [ABSTRACT FROM AUTHOR]

We investigate the maximum coding rate for a given average blocklength and error probability over a $K$ -user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiyet al.(2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e.,zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$ -user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaardet al.(2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case. [ABSTRACT FROM AUTHOR]

We investigate the maximum coding rate achievable on a two-user broadcast channel for the case where a common message is transmitted with feedback using either fixed-blocklength codes or variable-length codes. For the fixed-blocklength-code setup, we establish nonasymptotic converse and achievability bounds. An asymptotic analysis of these bounds reveals that feedback improves the second-order term compared to the no-feedback case. In particular, for a certain class of antisymmetric broadcast channels, we show that the dispersion is halved. For the variable-length-code setup, we demonstrate that the channel dispersion is zero. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of plausible deniability in an information theoretic framework. We consider a scenario where an entity that eavesdrops through a broadcast channel summons one of the parties in a communication protocol to reveal their message (or signal vector). It is desirable that the summoned party has enough freedom to produce a fake output that is likely plausible given the eavesdropper’s observation. We examine three variants of this problem—message deniability, transmitter deniability, and receiver deniability. In the first setting, the message sender is summoned to produce the sent message. Similarly, in the second and third settings, the transmitter and the receiver are required to produce the transmitted codeword and the received vector, respectively. For each of these settings, we examine the maximum communication rate that allows a given minimum rate of plausible fake outputs. First, for the message deniability problem, we fully characterize the capacity region for general broadcast channels. Next, for the transmitter deniability problem, we give an achievable region for general broadcast channels by fully characterizing the set of rate pairs’ achievable using deterministic coding schemes. Finally, for the receiver deniability problem, we give an achievable rate region for physically degraded broadcast channels. [ABSTRACT FROM AUTHOR]

The minrank of a directed graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al.), network coding (Effros et al.), and distributed storage (Mazumdar, ISIT, 2014). We prove tight bounds on the minrank of directed Erdős–Rényi random graphs $G(n,p)$ for all regimes of $p\in [{0,1}]$. In particular, for any constant $p$ , we show that $\mathsf {minrk}(G) = \Theta (n/\log n)$ with high probability, where $G$ is chosen from $G(n,p)$. This bound gives a near quadratic improvement over the previous best lower bound of $\Omega (\sqrt {n})$ (Haviv and Langberg), and partially settles an open problem raised by Lubetzky and Stav. Our lower bound matches the well-known upper bound obtained by the “clique covering” solution and settles the linear index coding problem for random knowledge graphs. [ABSTRACT FROM AUTHOR]

Privacy preserving data publishing (PPDP) provides methods for publishing colleting and stored information. For providing protection we have various privacy methods have been considered. In this paper give a brief sketch of number of anonymous techniques for privacy preserving micro data publishing. A number of anonymization techniques are designed for privacy preserving micro data publishing. Such a kind of Anonymization methods are Generalization and Bucketization. Coming to generalization us losses huge amount of information for high dimensional data. Because introducer can easily identify the information regarding particular person using quasi and sensitive attributes. Bucketization doesn't prevent the uniqueness discovery and have a clear disconnection between sensitive and quasi-identifier attribute. To defeat those drawbacks introduce a new method called as slicing. Slicing method can partition the data both vertically and horizontally. Slicing can also be used to prevent recognition disclosure, and the main advantage of slicing is managing me the high dimensional data or huge volume of information. Our investigational results shows that slicing is improved than generalization for data utility, and providing privacy preserving than bucketization. [ABSTRACT FROM AUTHOR]

Single-frequency networks (SFN) are widely adopted in terrestrial broadcast networks based on high-power high-tower (HPHT) deployments. The mobile broadcasting standard Evolved Multimedia Broadcast Multicast Service (eMBMS) has been enhanced in Release 14 to enable SFN operation with larger CP duration which may allow for the deployment of large area SFNs and even the combined operation between HPHT and low-power low-tower (LPLT) cellular stations. The knowledge of the signal-to-interference-plus-noise ratio (SINR) distribution over an SFN area may facilitate the selection of transmission parameters according to the network topology. This paper presents a semianalytical method for the calculation of the SINR distribution in SFNs with low computational complexity compared to Monte Carlo simulations. The method, which builds on previous work developed for cellular communications, is applied to HPHT+LPLT SFNs and evaluated against different transmission and network parameters. [ABSTRACT FROM PUBLISHER]

Ultrareliable point-to-multipoint communications are expected to become pivotal in networks offering future dependable services for smart cities. In this regard, sparse random linear network coding techniques have been widely employed to provide an efficient way to improve the reliability of broadcast and multicast data streams. This paper addresses the pressing concern of providing a tight approximation to the probability of a user recovering a data stream protected by this kind of coding technique. In particular, by exploiting the Stein–Chen method, we provide a novel and general performance framework applicable to any combination of system and service parameters, such as finite field sizes, lengths of the data stream, and level of sparsity. The deviation of the proposed approximation from Monte Carlo simulations is negligible, improving significantly on the state-of-the-art performance bounds. [ABSTRACT FROM PUBLISHER]

The Stinson–Wei traceability scheme (known as traceability scheme) was proposed for broadcast encryption as a generalization of the Chor–Fiat–Naor traceability scheme (known as traceability code). Cover-free family was introduced by Kautz and Singleton in the context of binary superimposed code. In this paper, we find a new relationship between a traceability scheme and a cover-free family, which strengthens the anti-collusion strength from t to t^{2} , i.e., a t$ -traceability scheme is a t^{2} -cover-free family. Based on this interesting discovery, we derive new upper bounds for traceability schemes. By using combinatorial structures, we construct several infinite families of optimal traceability schemes, which attain our new upper bounds. We also provide a constructive lower bound for traceability schemes, the size of which has the same order of magnitude as our general upper bound. Meanwhile, we consider parent-identifying set systems, an anti-collusion key-distributing scheme requiring weaker conditions than traceability scheme but stronger conditions than cover-free family. A new upper bound is also given for parent-identifying set systems. [ABSTRACT FROM PUBLISHER]

Data broadcasting has become the preferred method to dispense data to a large number of mobile users. Current researches on on-demand data broadcast mainly propose algorithms based on a single broadcast channel or fixed multi-channel, i.e., fixed channel model. As a result of the dynamic diversity of data characteristics and client demands, the fixed channel model faces significant challenges in parallel broadcast diverse data. Further, the dynamic adjustment of the broadcast channel (dynamic channel model) based on client requests is favorable to service quality because it determines the number and sizes of channels that adapt to client demand in real-time. However, the dynamic channel model has not yet been thoroughly investigated for on-demand wireless data broadcasts. Accordingly, in this paper, a channel dynamic adjustment method (CDAM) is proposed. The innovations behind CDAM lie in three aspects. First, a data item priority evaluation and selection algorithm (S-RxW/SL) is proposed for evaluating the priority of data items and selecting the high priority data items to be considered in a broadcast cycle. Second, a weight and size average cluster algorithm (WSAC) is proposed for mining data item characteristics and clustering them. Third, based on the clustering results of WSAC, a channel splitting and data allocation algorithm (CSDA) is proposed for dynamically splitting the channel and allocating data items to the corresponding sub-channel. We compare the proposed method with some state-of-the-art scheduling methods through simulation. The theoretical findings and simulation results reveal that significantly better request loss rate (LR) can be obtained by using our method as compared to its alternatives. [ABSTRACT FROM AUTHOR]

This paper investigates a joint source-channel secrecy problem for the Shannon cipher broadcast system. We suppose list secrecy is applied, i.e., a wiretapper is allowed to produce a list of reconstruction sequences and the secrecy is measured by the minimum distortion over the entire list. For discrete communication cases, we propose a permutation-based uncoded scheme, which cascades a random permutation with a symbol-by-symbol mapping. Using this scheme, we derive an inner bound for the admissible region of secret key rate, list rate, wiretapper distortion, and distortions of legitimate users. For the converse part, we easily obtain an outer bound for the admissible region from an existing result. Comparing the outer bound with the inner bound shows that the proposed scheme is optimal under certain conditions. Besides, we extend the proposed scheme to the scalar and vector Gaussian communication scenarios, and characterize the corresponding performance as well. For these two cases, we also propose another uncoded scheme, orthogonal-transform-based scheme, which achieves the same performance as the permutation-based scheme. Interestingly, by introducing the random permutation or the random orthogonal transform into the traditional uncoded scheme, the proposed uncoded schemes, on one hand, provide a certain level of secrecy, and on the other hand, do not lose any performance in terms of the distortions for legitimate users. [ABSTRACT FROM PUBLISHER]

Given a set of multiple channels, a set of multiple requests, where each request contains multiple requested data items and a client equipped with multiple antennae, the multi-antenna-based multirequest data retrieval problem (DRMR-MA) is to find a data retrieval sequence for downloading all data items of the requests allocated to each antenna, such that the maximum access latency of all antennae is minimized. Most existing approaches for the data retrieval problem focus on either single antenna or single request and are hence not directly applicable to DRMR-MA for retrieving multiple requests. This paper proposes two data retrieval algorithms that adopt two different grouping schemes to solve DRMR-MA so that the requests can be suitably allocated to each antenna. To find the data retrieval sequence of each request efficiently, we present a data retrieval scheme that converts a wireless data broadcast system to a special tree. Experimental results show that the proposed scheme is more efficient than other existing schemes. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorithm for maximal independent set selection operates on a network of identical anonymous processors. The processor at each node has no prior information about the network. At each time step, each node can only broadcast a single bit to all its neighbours, or remain silent. Each node can detect whether one or more neighbours have broadcast, but cannot tell how many of its neighbours have broadcast, or which ones. We build on recent work of Afek et al. (Science 331(6014):183-185, 2011) which was inspired by studying the development of a network of cells in the fruit fly. However we incorporate for the first time another important feature of the biological system: varying the probability value used at each node based on local feedback from neighbouring nodes. Given any n-node network, our algorithm achieves with high probability the optimal time complexity of $$O(\log n)$$ rounds and the optimal expected message complexity of O(1) single-bit messages broadcast by each node. We also show that the previous approach, without feedback, cannot achieve better than $$\varOmega (\log ^2 n)$$ time complexity with high probability, whatever global scheme is used to choose the probabilities. Our algorithm for distributed greedy colouring works under similar harsh conditions: each identical node has no prior information about the network, can only broadcast a single message to all neighbours at each time step representing a desired colour, and can only detect whether at least one neighbour has broadcast each colour value. We show that with high probability our algorithm has a time complexity of $$O(\Delta +\log n)$$ , where $$\Delta $$ is the maximum degree of the network, and also has an expected message complexity of O(1) messages broadcast by each node. [ABSTRACT FROM AUTHOR]

We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS '00, 2000). In the phone call model, in every time step, each node calls a randomly chosen neighbour to establish a communication channel to this node. The communication channels can then be used bi-directionally to transmit messages. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node required to broadcast a message efficiently decreases exponentially. Formally, we present an algorithm that has time complexity $$O(\log n)$$ and uses $$O(n\log \log n)$$ transmissions per message. In contrast, we show for the standard model that every distributed algorithm in a restricted address-oblivious model that broadcasts a message in time $$O(\log n)$$ requires $$\Omega (n \log n{/} \log d)$$ message transmissions. Our algorithm efficiently handles limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases. [ABSTRACT FROM AUTHOR]

This paper presents a novel scheme to transmit signals in a Multiuser Multiple-Input Multiple-Output (MU-MIMO) downlink scenario. The proposed scheme combines Block Diagonalization (BD) and Generalized Spatial Modulation (SM) Techniques. The SM technique is used to add a broadcast transmission to the conventional MU-MIMO BD scheme, which results in a novel BDSM proposal. We compare the proposed BDSM scheme with the conventional BD scheme considering the Bit Error Rate (BER) performance, detection complexity, and spectral efficiency using Maximum Likelihood (ML) joint-detection and ML segmented-detection algorithms. A correlated fading channel with Rayleigh distribution is considered. Simulations results show that the broadcast transmission can be added to the BD scheme without performance impairment. The proposed BDSM system has performance gains of 4 dB for error rates of 10 −3 approximately when some bits are considered as broadcast transmission in the BD scheme. In general, the proposed detection algorithms have a tradeoff between the BER performance and the detector’s complexity. [ABSTRACT FROM AUTHOR]

We consider the problem of multiple-input single-output broadcast channels with Rayleigh fading where the transmitter has access to delayed knowledge of the channel state information. We first characterize the capacity region of this channel with two users to within constant number of bits for all values of the transmit power. The proposed signaling strategy utilizes the delayed knowledge of the channel state information and the previously transmitted signals, in order to create a signal of common interest for both receivers. This signal would be the quantized version of the summation of the previously transmitted signals. A challenge that arises in deriving the result for finite signal-to-noise ratio regimes is the correlation that exists between the quantization noise and the signal. To guarantee the independence of quantization noise and signal, we extend the framework of lattice quantizers with dither together with an interleaving step. For converse, we use the fact that the capacity region of this problem is upper bounded by the capacity region of a physically degraded broadcast channel with no channel state information where one receiver has two antennas. Then, we derive an outer bound on the capacity region of this degraded broadcast channel. Finally, we show how to extend our results to obtain the approximate capacity of the $K$ -user multiple-input single-output broadcast channel with delayed knowledge of the channel state information at the transmitter to within 2 \log _{2} ( K \,\, + 2 ) bits/s/Hz. [ABSTRACT FROM AUTHOR]

Mobile-relay-assisted forwarding in delay-tolerant networks (DTNs) can improve network capacity and packet delivery ratio but, at the same time, may significantly increase energy consumption at the system level. In this paper, we propose a distance-based energy-efficient opportunistic forwarding (DEEOF) framework for the broadcast transmission in mobile DTNs. DEEOF strikes a balance between energy consumption and network performance by maximizing the energy efficiency while maintaining a high packet delivery ratio. In the proposed algorithms, we define the metric of the forwarding equivalent energy efficiency distance (FEED) for broadcast transmission to quantify the transmission distances achieving the same energy efficiency at different time instances, or with different numbers of the relays in the source's transmission radius. Based on the concept of FEED, we propose two DEEOF algorithms for opportunistic broadcast forwarding, which makes the forwarding decision by comparing the current energy efficiency with the estimated future expectation and distribution, respectively. The performance improvement of the proposed DEEOF algorithms is also demonstrated by simulation, particularly for the cases in which the source has very limited battery reserves. [ABSTRACT FROM AUTHOR]

Though a cooperative broadcast scheme has been proposed for fading environments, it has two defects: First, it only handles a packet flow from a single source node in the network, but does not consider the scenario of multiple packet flows simultaneously broadcasted from different source nodes. Second, it only allows a single relay node to forward a packet in each time slot, though multiple relay nodes forwarding in a time slot can significantly reduce broadcast latency. In this paper, we aim achieve low-latency multi-flow broadcast in wireless multi-hop networks with fading channels. To describe the interference among the transmission in different flows, we incorporate the Rayleigh fading model to the signal to noise ratio (SNR) model. Then, we introduce a cooperative diversity scheme which allows multiple relays forwarding in a time slot to reduce broadcast latency. We then formulate an interesting problem: In a fading environment, what is the optimal relay allocation schedule to minimize the broadcast latency? We propose a warm up heuristic algorithm for single-flow cooperative broadcast, based on which, we further propose a heuristic algorithm for multi-flow cooperative broadcast. Simulation results demonstrate that the two algorithms achieve lower broadcast latency than a previous method. [ABSTRACT FROM PUBLISHER]

This paper introduces the covering dimension of a linear code over a finite field, which is analogous to the critical exponent of a representable matroid and, thus, generalizes invariants that lie at the heart of several fundamental problems in a coding theory. An upper bound on the covering dimension is proved, improving Kung’s classical bound for the critical exponent. In addition, a construction is given for linear codes that attain equality in this covering dimension bound. [ABSTRACT FROM AUTHOR]

We develop a low-complexity polar coding scheme for the discrete memoryless broadcast channel with confidential messages under strong secrecy and randomness constraints. Our scheme extends previous work by using an optimal rate of uniform randomness in the stochastic encoder, and avoiding assumptions regarding the symmetry or degraded nature of the channels. The price paid for these extensions is that the encoder and the decoders are required to share a secret seed of negligible size and to increase the block length through chaining. We also highlight a close conceptual connection between the proposed polar coding scheme and a random binning proof of the secrecy capacity region. [ABSTRACT FROM AUTHOR]

We investigate multi-point algebraic geometric codes defined from curves related to the generalized Hermitian curve introduced by Bassa et al. Our main result is to find a basis of the Riemann–Roch space of a series of divisors, which can be used to construct multi-point codes explicitly. These codes turn out to have nice properties similar to those of Hermitian codes, for example, they are easy to describe, to encode and decode. It is shown that the duals are also such codes and an explicit formula is given. In particular, this formula enables one to calculate the parameters of these codes. Finally, we apply our results to obtain linear codes attaining new records on the parameters. A new record-giving [234, 141,≥ 59]-code over \mathbb F27 is presented as one of the examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new way of providing cyclic structures to convolutional codes. We define the skew cyclic convolutional codes as left ideals of a quotient ring of a suitable non-commutative polynomial ring. In contrast to the previous approaches to cyclicity for convolutional codes, we use Ore polynomials with coefficients in a field (the rational function field over a finite field), so their arithmetic is very well known and we may proceed similarly to cyclic block codes. In particular, we show how to obtain easily skew cyclic convolutional codes of a given dimension, and we compute an idempotent generator of the code and its dual. [ABSTRACT FROM AUTHOR]

This paper presents an outage analysis for a two-user parallel Gaussian interference channel consisting of two sub-channels. Each sub-channel is modeled as a two-user Gaussian interference channel with quasi-static and flat fading. Both users employ single-layer Gaussian code-books and maintain a statistical correlation \rho between the signals transmitted over the underlying sub-channels. When joint decoding (JD) is performed at the receivers, setting \rho =0 minimizes the outage probability, regardless of the value of the signal-to-noise ratio (SNR). It is shown, however, that if the receivers treat interference as noise (TIN) or cancel interference (CI), the value of optimum \rho approaches 1 as SNR goes to infinity. Motivated by these observations, we let \rho =0 under JD and \rho =1 , it is shown that the outage probability scales like \mathrm snr^-(1-r) under both TIN and CI, while it vanishes at least as fast as \mathrm snr^-\min \2-r,4(1-r)\\log \mathrm snr under JD. This paper is concluded by extending some of the results to a two-user parallel Gaussian interference channel with an arbitrary number of sub-channels. [ABSTRACT FROM AUTHOR]

This paper investigates various subtleties of applying linear physical-layer network coding (PNC) with $q$ -level pulse amplitude modulation ( $q$ -PAM) in two-way relay channels. A critical issue is how the PNC system performs when the received powers from the two users at the relay are imbalanced. In particular, how would the PNC system perform under slight power imbalance that is inevitable in practice, even when power control is applied? To answer these questions, this paper presents a comprehensive analysis of $q$ -PAM PNC. Our contributions are as follows. First, we give a systematic way to obtain the analytical relationship between the minimum distance of the signal constellation induced by the superimposed signals of the two users (a key performance determining factor) and the channel-gain ratio of the two users, for all $q$ . In particular, we show how the minimum distance changes in a piecewise linear fashion as the channel-gain ratio varies. Second, we show that the performance of $q$ -PAM PNC is highly sensitive to imbalanced received powers from the two users at the relay, even when the power imbalance is slight (e.g., the residual power imbalance in a power-controlled system). This sensitivity problem is exacerbated as $q$ increases, calling into question the robustness of high-order modulated PNC. Third, we propose an asynchronized PNC system in which the symbol arrival times of the two users at the relay are deliberately made to be asynchronous. We show that such asynchronized PNC, when operated with a belief propagation decoder, can remove the sensitivity problem, allowing a robust high-order modulated PNC system to be built. [ABSTRACT FROM AUTHOR]

We consider an n -relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive schedule. Even for the moderate values of n different states for the network (since each of the relays can be in either transmitting or receiving mode). In this paper, we investigate whether a significant fraction of the network capacity can be achieved by using transmit/receive schedules that have only few active states and by using only few relays. First, we conjecture that the approximately optimal schedule has at most n+1 states instead of the 2^n possible states. We prove this conjecture for networks of size n\leq 6 by developing a proof strategy and implementing it computationally. Second, we show that routing strategies that only employ the point-to-point communication and two of the relays with a half-duplex schedule that has only two active states can achieve at least half the capacity (approximately) of the network. Techniques from linear programming and submodular functions are used to derive the results. [ABSTRACT FROM AUTHOR]

An ordering between the quantum states emerging from a single-mode gauge-covariant bosonic Gaussian channel is proved. Specifically, we show that within the set of input density matrices with the same given spectrum, the element passive with respect to the Fock basis (i.e., diagonal with decreasing eigenvalues) produces an output, which majorizes all the other outputs emerging from the same set. When applied to pure input states, our finding includes as a special case the result of Mari et al., Nat. Comm. 5, 3826 (2014) which implies that the output associated to the vacuum majorizes the others. [ABSTRACT FROM AUTHOR]

The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is independently connected with probability $p$ within clusters and $q$ across clusters. In the asymptotic regime of $p=a \log n/n$ and $q=b \log n/n$ for fixed $a,b$ , and $n \to \infty $ , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to $n$ . [ABSTRACT FROM AUTHOR]

This paper introduces Manhattan sampling in two and higher dimensions, and proves sampling theorems for them. In 2-D, Manhattan sampling, which takes samples densely along a Manhattan grid of lines, can be viewed as sampling on the union of two rectangular lattices, one dense horizontally and the other vertically, with the coarse spacing of each being a multiple of the fine spacing of the other. The sampling theorem shows that the images bandlimited to the union of the Nyquist regions of the two rectangular lattices can be recovered from their Manhattan samples, and an efficient procedure for doing so is given. Such recovery is possible even though there is an overlap among the spectral replicas induced by Manhattan sampling. In three and higher dimensions, there are many possible configurations for Manhattan sampling, each consisting of the union of special rectangular lattices called bi-step lattices. This paper identifies them, proves a sampling theorem showing that the images bandlimited to the union of the Nyquist regions of the bi-step rectangular lattices are recoverable from Manhattan samples, presents an efficient onion-peeling procedure for doing so, and shows that the union of Nyquist regions is as large as any bandlimited region, such that all images supported by such can be stably reconstructed from samples taken at the rate of the Manhattan sampling. It also develops a special representation for the bi-step lattices with a number of useful properties. While most of this paper deals with continuous-space images, Manhattan sampling of discrete-space images is also considered, for infinite, as well as finite, support images. [ABSTRACT FROM AUTHOR]

In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over n -bit vectors taking m -bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function f:G\rightarrow \mathcal R , where G = (\mathbb F2^{n},+) is the group of n bit vectors with bitwise modulo two addition +, and {\mathcal{ R}} is a finite commutative ring of characteristic 2. Using the specific group structure of G and a sequence of nested subgroups of G , we define the fast TMFT and its inverse. Since the image {\mathcal{ R}} of the binary functions is a ring, we can define the convolution between two functions f:G\rightarrow {\mathcal{ R}}$ . We then provide the TMFT properties, including the convolution theorem, which can be used to efficiently compute convolutions. Finally, we derive the complexity of the fast TMFT and the inverse fast TMFT. [ABSTRACT FROM AUTHOR]

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide. [ABSTRACT FROM AUTHOR]

The quantum relative entropy between two states satisfies a monotonicity property meaning that applying the same quantum channel to both states can never increase their relative entropy. It is known that this inequality is only tight when there is a recovery map that exactly reverses the effects of the quantum channel on both states. In this paper, we strengthen this inequality by showing that the difference of relative entropies is bounded below by the measured relative entropy between the first state and a recovered state from its processed version. The recovery map is a convex combination of rotated Petz recovery maps and perfectly reverses the quantum channel on the second state. As a special case, we reproduce recent lower bounds on the conditional mutual information, such as the one proved by Fawzi and Renner. Our proof only relies on the elementary properties of pinching maps and the operator logarithm. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new channel model, which we name the $q$ -ary partial erasure channel (QPEC). The QPEC has a $q$ -ary input, and its output is either the input symbol or a set of $M$ ( $2 \le M \le q$ ) symbols, containing the input symbol. This channel serves as a generalization to the binary erasure channel and mimics situations when a symbol output from the channel is known only partially; that is, the output symbol contains some ambiguity, but is not fully erased. This type of channel is motivated by non-volatile memory multi-level read channels. In such channels, the readout is obtained by a sequence of current/voltage measurements, which may terminate with a partial knowledge of the stored level. Our investigation is concentrated on the performance of low-density parity-check (LDPC) codes when used over this channel, thanks to their low decoding complexity using belief propagation. We provide the exact QPEC density-evolution equations that govern the decoding process, and suggest a cardinality-based approximation as a proxy. We then provide several bounds and approximations on the proxy density evolutions, and verify their tightness through numerical experiments. Finally, we provide tools for the practical design of LDPC codes for use over the QPEC. [ABSTRACT FROM AUTHOR]

The squashed entanglement of a quantum channel is an additive function of quantum channels, which finds application as an upper bound on the rate at which secret key and entanglement can be generated when using a quantum channel a large number of times in addition to unlimited classical communication. This quantity has led to an upper bound of $\log ((1+\eta )/(1-\eta ))$ on the capacity of a pure-loss bosonic channel for such a task, where $\eta $ is the average fraction of photons that make it from the input to the output of the channel. The purpose of this paper is to extend these results beyond the single-sender single-receiver setting to the more general case of a single sender and multiple receivers (a quantum broadcast channel). We employ multipartite generalizations of the squashed entanglement to constrain the rates at which secret key and entanglement can be generated between any subset of the users of such a channel, along the way developing several new properties of these measures. We apply our results to the case of a pure-loss broadcast channel with one sender and two receivers. [ABSTRACT FROM AUTHOR]

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions f:A^n\to A^n over a finite alphabet $A$ (usually referred to as Boolean networks if A = \{0,1\} ) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs. [ABSTRACT FROM AUTHOR]

We construct an explicit family of \mathbb Fh -linear rank-metric codes over any field \mathbb Fh that enables efficient list-decoding up to a fraction $\rho $ of errors in the rank metric with a rate of 1-\rho - \varepsilon $ , for any desired \rho \in (0,1)$ and \varepsilon > 0 that arise in our linear-algebraic list decoder for Gabidulin codes. This subspace is obtained by combining subspace designs constructed by Guruswami and Kopparty (FOCS’13) with subspace-evasive varieties due to Dvir and Lovett (STOC’12). We establish a similar result for subspace codes, which have received much attention recently in the context of network coding. We also give explicit subcodes of folded Reed–Solomon (RS) codes with small folding order, which are list-decodable (in the Hamming metric) with optimal redundancy, motivated by the fact that list-decoding RS codes reduces to list-decoding such folded RS codes. However, as we only list-decode a subcode of these codes, the Johnson radius continues to be the best known error fraction for list-decoding RS codes. [ABSTRACT FROM AUTHOR]

Two alternative exact characterizations of the minimum error probability of Bayesian $M$ -ary hypothesis testing are derived. The first expression corresponds to the error probability of an induced binary hypothesis test and implies the tightness of the meta-converse bound by Polyanskiy et al.; the second expression is a function of an information-spectrum measure and implies the tightness of a generalized Verdú-Han lower bound. The formulas characterize the minimum error probability of several problems in information theory and help to identify the steps where existing converse bounds are loose. [ABSTRACT FROM AUTHOR]

Consider the recovery of an unknown signal x from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that x is sparse, and that the measurements are of the form \mathop \mathrm sign\kern 0pt\nolimits (\langle ai, {x} \rangle ) \in \{\pm 1\} . Since such measurements give no information on the norm of x , recovery methods typically assume that \| x \|2=1 . We show that if one allows more generally for quantized affine measurements of the form \mathop \mathrm sign\kern 0pt\nolimits (\langle ai, {x} \rangle + bi) , and if the vectors ai are random, an appropriate choice of the affine shifts bi allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. In addition, we show that for arbitrary fixed x in the annulus r \leq \| x \|2 \leq R , one may estimate the norm \| x \|2 up to additive error $\delta $ from m {\gtrsim } R^{4} r^{-2} \delta ^{-2} such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors x in a Euclidean ball of known radius. [ABSTRACT FROM PUBLISHER]

The usefulness of Gabor frames depends on the easy computability of a suitable dual window. This question is addressed under several aspects. Several versions of Schulz’s iterative algorithm for the approximation of the canonical dual window are analyzed for their numerical stability. For Gabor frames with totally positive windows or with exponential B-splines, a direct algorithm yields a family of exact dual windows with compact support. It is shown that these dual windows converge exponentially fast to the canonical dual window. [ABSTRACT FROM AUTHOR]

We generalize Helberg’s number-theoretic construction of binary multiple insertion/deletion correcting codes to non-binary alphabets and describe a linear decoding algorithm for correcting multiple deletions. [ABSTRACT FROM AUTHOR]

We analyze the asymptotic performance of nonbinary spatially coupled low-density parity-check (SC-LDPC) code ensembles defined over the general linear group on the binary erasure channel. In particular, we prove the threshold saturation of belief propagation decoding to the so-called potential threshold, using the proof technique based on potential functions introduced by Yedla et al., assuming that the potential function exists. We rewrite the density evolution of nonbinary SC-LDPC codes in an equivalent vector recursion form which is suited for the use of the potential function. We then discuss the existence of the potential function for the general case of vector recursions defined by multivariate polynomials, and give a method to construct it. We define a potential function in a slightly more general form than the one by Yedla et al., in order to make the technique based on potential functions applicable to the case of nonbinary LDPC codes. We show that the potential function exists if a solution to a carefully designed system of linear equations exists. Furthermore, we numerically show the existence of a solution to the system of linear equations for a large number of nonbinary LDPC code ensembles, which allows us to define their potential function and thus prove threshold saturation. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a sequence of discrete Fourier transforms and define new versions of bent functions, which we shall call (weak and strong) octa/hexadeca and, in general, 2^k -bent functions. We investigate relationships between these classes and completely characterize the octabent and hexadecabent functions in terms of bent functions. We further find relative difference sets based upon these functions. [ABSTRACT FROM AUTHOR]

We investigate compressibility of the dimension of positive semidefinite matrices, while approximately preserving their pairwise inner products. This can either be regarded as compression of positive semidefinite factorizations of nonnegative matrices or (if the matrices are subject to additional normalization constraints) as compression of quantum models. We derive both lower and upper bounds on compressibility. Applications are broad and range from the analysis of experimental data to bounding the one-way quantum communication complexity of Boolean functions. [ABSTRACT FROM AUTHOR]

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles. [ABSTRACT FROM AUTHOR]

In this paper, we study a security problem on a simple wiretap network, consisting of a source node S, a destination node D, and an intermediate node R. The intermediate node connects the source and the destination nodes via a set of noiseless parallel channels, with sizes n1 and n2 , respectively. A message $M$ is to be sent from S to D. The information in the network may be eavesdropped by a set of wiretappers. The wiretappers cannot communicate with one another. Each wiretapper can access a subset of channels, called a wiretap set. All the chosen wiretap sets form a wiretap pattern. A random key $K$ is generated at S, and a coding scheme on $(M, K)$ is employed to protect $M$ . We define two decoding classes at D. In Class-I, only $M$ is required to be recovered, and in Class-II, both $M$ and $K$ are required to be recovered. The objective is to minimize $H(K)/H(M)$ for a given wiretap pattern under the perfect secrecy constraint. The first question we address is whether routing is optimal on this simple network. By enumerating all the wiretap patterns on the Class-I/II (3, 3) networks and harnessing the power of Shannon-type inequalities, we find that gaps exist between the bounds implied by routing and the bounds implied by Shannon-type inequalities for a small fraction (<2%) of all the wiretap patterns. The second question we investigate is the following: What is $\min H(K)/H(M)$ for the remaining wiretap patterns where gaps exist? We study some simple wiretap patterns and find that their Shannon bounds (i.e., the lower bound induced by Shannon-type inequalities) can be achieved by linear codes, which means routing is not sufficient even for the (3, 3) network. For some complicated wiretap patterns, we study the structures of linear coding schemes under the assumption that they can achieve the corresponding Shannon bounds. This paper indicates that the determination of the entropic region of six linear vector spaces cannot be sidestepped. Some subtle issues on the network models are discussed, and interesting observations are stated. [ABSTRACT FROM AUTHOR]

Lifted Reed–Solomon codes are a natural affine-invariant family of error-correcting codes, which generalize Reed–Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable with the known algorithms for Reed–Muller codes), but with significantly better rate. We give efficient algorithms for list decoding and local list decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that the codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field). [ABSTRACT FROM AUTHOR]