Computer Science - Information Theory Publications (50)


Computer Science - Information Theory Publications

In this article we consider the problem of generating pseudo-random matrices based on the similarity of their spectra to Wigner's semicircular law. We introduce $r$-independent pseudo-Wigner ensembles and prove closeness of their spectra to the semicircular density in Kolmogorov metric. We give an explicit construction of a family of pseudo-Wigner ensembles using dual BCH codes and show that the Kolmogorov complexity of the constructed matrices is comparatively low. Read More

A promising research area that has recently emerged, is on how to use index coding to improve the communication efficiency in distributed computing systems, especially for data shuffling in iterative computations. In this paper, we posit that pliable index coding can offer a more efficient framework for data shuffling, as it can better leverage the many possible shuffling choices to reduce the number of transmissions. We theoretically analyze pliable index coding under data shuffling constraints, and design an hierarchical data-shuffling scheme that uses pliable coding as a component. Read More

For vector Gaussian channels, a precise differential connection between channel capacity and a quantity termed normalized optimal detection error (NODE) is presented. Then, this C-NODE relationship is extended to continuous-time Gaussian channels drawing on a waterfilling characterization recently found for the capacity of continuous-time linear time-varying channels. In the latter case, the C-NODE relationship becomes asymptotic in nature. Read More

This paper presents a new technique for providing the analysis and comparison of wiretap codes in the small blocklength regime over the binary erasure wiretap channel. A major result is the development of Monte Carlo strategies for quantifying a code's equivocation, which mirrors techniques used to analyze normal error correcting codes. For this paper, we limit our analysis to coset-based wiretap codes, and make several comparisons of different code families at small and medium blocklengths. Read More

A cognitive radio system has the ability to observe and learn from the environment, adapt to the environmental conditions, and use the radio spectrum more efficiently. However, due to multipath fading, shadowing, or varying channel conditions, uncertainty affects the cognitive cycle processes, measurements, decisions, and actions. In the observing step, measurements (i. Read More

Energy harvesting (EH) has been developed to extend the lifetimes of energy-limited communication systems. In this letter, we consider a single-user EH communication system, in which both of the arrival data and the harvested energy curves are modeled as general functions. Unlike most of the works in the field, we investigate the online algorithms which only acquire the causal information of the arrival data and the harvested energy processes. Read More

The sequential analysis of the problem of joint signal detection and signal-to-noise ratio (SNR) estimation for a linear Gaussian observation model is considered. The problem is posed as an optimization setup where the goal is to minimize the number of samples required to achieve the desired (i) type I and type II error probabilities and (ii) mean squared error performance. This optimization problem is reduced to a more tractable formulation by transforming the observed signal and noise sequences to a single sequence of Bernoulli random variables; joint detection and estimation is then performed on the Bernoulli sequence. Read More

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. Read More

In this paper, we propose a novel reception/transmission scheme for half-duplex base stations (BSs). In particular, we propose a half-duplex BS that employes in-band uplink-receptions from user 1 and downlink-transmissions to user 2, which occur in different time slots. Furthermore, we propose optimal adaptive scheduling of the in-band uplink-receptions and downlink-transmissions of the BS such that the uplink-downlink rate/throughput region is maximized and the outage probabilities of the uplink and downlink channels are minimized. Read More

In this paper, we analyze downlink non-orthogonal multiple access (NOMA) networks with limited feedback. Our goal is to derive appropriate transmission rates for rate adaptation and minimize outage probability of minimum rate for the constant-rate data service, based on distributed channel feedback information from receivers. We propose an efficient quantizer with variable-length encoding that approaches the best performance of the case where perfect channel state information is available anywhere. Read More

Given two discrete random variables $X$ and $Y$, with probability distributions ${\bf p} =(p_1, \ldots , p_n)$ and ${\bf q}=(q_1, \ldots , q_m)$, respectively, denote by ${\cal C}({\bf p}, {\bf q})$ the set of all couplings of ${\bf p}$ and ${\bf q}$, that is, the set of all bivariate probability distributions that have ${\bf p}$ and ${\bf q}$ as marginals. In this paper, we study the problem of finding the joint probability distribution in ${\cal C}({\bf p}, {\bf q})$ of minimum entropy (equivalently, the joint probability distribution that maximizes the mutual information between $X$ and $Y$), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in ${\cal C}({\bf p}, {\bf q})$ with entropy exceeding the minimum possible by at most 1, thus providing an approximation algorithm with additive approximation factor of 1. Read More

A locally recoverable code is a code over a finite alphabet such that the value of any single coordinate of a codeword can be recovered from the values of a small subset of other coordinates. Building on work of Barg, Tamo, and Vl\u{a}du\c{t}, we present several constructions of locally recoverable codes from algebraic curves and surfaces. Read More

We present a new family of one-coincidence sequence sets suitable for frequency hopping code division multiple access (FH-CDMA) systems with dispersed (low density) sequence elements. These sets are derived from one-coincidence prime sequence sets, such that for each one-coincidence prime sequence set there is a new one-coincidence set comprised of sequences with dispersed sequence elements, required in some circumstances, for FH-CDMA systems. Getting rid of crowdedness of sequence elements is achieved by doubling the size of the sequence element alphabet. Read More

A massive MIMO system entails a large number (tens or hundreds) of base station antennas serving a much smaller number of terminals. These systems demonstrate large gains in spectral and energy efficiency compared with conventional MIMO technology. As the number of antennas grows, the performance of a massive MIMO system gets limited by the interference caused by pilot contamination. Read More

One of the most promising approaches to overcome the uncertainty and dynamic channel variations of millimeter wave (mmW) communications is to deploy dual-mode base stations that integrate both mmW and microwave ($\mu$W) frequencies. If properly designed, such dual-mode base stations can enhance mobility and handover in highly mobile wireless environments. In this paper, a novel approach for analyzing and managing mobility in joint $\mu$W-mmW networks is proposed. Read More

Mobile-edge computing (MEC) has emerged as a prominent technique to provide mobile services with high computation requirement, by migrating the computation-intensive tasks from the mobile devices to the nearby MEC servers. To reduce the execution latency and device energy consumption, in this paper, we jointly optimize task offloading scheduling and transmit power allocation for MEC systems with multiple independent tasks. A low-complexity sub-optimal algorithm is proposed to minimize the weighted sum of the execution delay and device energy consumption based on alternating minimization. Read More

This paper is devoted to the study of the construction of new quantum MDS codes. Based on constacyclic codes over Fq2 , we derive four new families of quantum MDS codes, one of which is an explicit generalization of the construction given in Theorem 7 in [22]. We also extend the result of Theorem 3:3 given in [17]. Read More

We prove the Courtade-Kumar conjecture, for several classes of n-dimensional Boolean functions, for all $n \geq 2$ and for all values of the error probability of the binary symmetric channel, $0 \leq p \leq 1/2$. This conjecture states that the mutual information between any Boolean function of an n-dimensional vector of independent and identically distributed inputs to a memoryless binary symmetric channel and the corresponding vector of outputs is upper-bounded by $1-\operatorname{H}(p)$, where $\operatorname{H}(p)$ represents the binary entropy function. That is, let $\mathbf{X}=[X_1 \ldots X_n]$ be a vector of independent and identically distributed Bernoulli(1/2) random variables, which are the input to a memoryless binary symmetric channel, with the error probability in the interval $0 \leq p \leq 1/2$ and $\mathbf{Y}=[Y_1 \ldots Y_n]$ the corresponding output. Read More

For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to general source model without helpers or wiretapper's side information but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, the results give rise to a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate. Read More

Stochastic dynamic control systems relate in a prob- abilistic fashion the space of control signals to the space of corresponding future states. Consequently, stochastic dynamic systems can be interpreted as an information channel between the control space and the state space. In this work we study this control-to-state informartion capacity of stochastic dynamic systems in continuous-time, when the states are observed only partially. Read More

The capacity of the discrete-time channel affected by both additive Gaussian noise and Wiener phase noise is studied. Novel inner and outer bounds are presented, which differ of at most $6.65$ bits per channel use for all channel parameters. Read More

In this paper, we obtain new sum capacity results for the Gaussian many-to-one and one-to-many interference channels. Simple Han-Kobayashi (HK) schemes, i.e. Read More

Considering a multiple-user multiple-input multiple-output (MIMO) channel with an eavesdropper, this letter develops a beamformer design to optimize the energy efficiency in terms of secrecy bits per Joule under secrecy quality-of-service constraints. This is a very difficult design problem with no available exact solution techniques. A path-following procedure, which iteratively improves its feasible points by using a simple quadratic program of moderate dimension, is proposed. Read More

Using a broadcast channel to transmit clients' data requests may impose privacy risks. In this paper, we address such privacy concerns in the index coding framework. We show how a malicious client can infer some information about the requests and side information of other clients by learning the encoding matrix used by the server. Read More

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. Read More

This paper investigates the error probability of a stochastic decision and the way in which it differs from the error probability of an optimal decision, i.e., the maximum a posteriori decision. Read More

An agglomerative clustering of random variables is proposed, where clusters of random variables sharing the maximum amount of multivariate mutual information are merged successively to form larger clusters. Compared to the previous info-clustering algorithms, the agglomerative approach allows the computation to stop earlier when clusters of desired size and accuracy are obtained. An efficient algorithm is also derived based on the submodularity of entropy and the duality between the principal sequence of partitions and the principal sequence for submodular functions. Read More

Estimating the angular separation between two incoherently radiating monochromatic point sources is a canonical toy problem to quantify spatial resolution in imaging. In recent work, Tsang {\em et al.} showed, using a Fisher Information analysis, that Rayleigh's resolution limit is just an artifact of the conventional wisdom of intensity measurement in the image plane. Read More

We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are $n$ clusters in total, with $m$ nodes per cluster. A data file is coded and stored across the $mn$ nodes, with each node storing $\alpha$ symbols. Read More

We consider a cognitive radio network in a multi-channel licensed environment. Secondary user transmits in a channel if the channel is sensed to be vacant. This results in a tradeoff between sensing time and transmission time. Read More

In this work we characterize all ambiguities of the linear (aperiodic) one-dimensional convolution on two fixed finite-dimensional complex vector spaces. It will be shown that the convolution ambiguities can be mapped one-to-one to factorization ambiguities in the $z-$domain, which are generated by swapping the zeros of the input signals. We use this polynomial description to show a deterministic version of a recently introduced masked Fourier phase retrieval design. Read More

A new synthesis scheme is proposed to effectively generate a random vector with prescribed joint density that induces a (latent) Gaussian tree structure. The quality of synthesis is measured by total variation distance between the synthesized and desired statistics. The proposed layered and successive encoding scheme relies on the learned structure of tree to use minimal number of common random variables to synthesize the desired density. Read More

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. Read More

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. Read More

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 \emph{displacement convex} and that the minimizers are given by the fixed points of the recursions. Read More

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. Read More

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. Read More

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. Read More

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. Read More

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. Read More

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{\i}kan-style transformations are continuous. Read More

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. Read More

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. Read More

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. Read More

Bri\"et et al. showed that an efficient communication protocol implies a reliable XOR game protocol. In this work, we improve this relationship, and obtain a nontrivial lower bound $2\log3\approx 3. Read More

We consider the dynamics of message passing for spatially coupled codes and, in particular, the set of density evolution equations that tracks the profile of decoding errors along the spatial direction of coupling. It is known that, for suitable boundary conditions and after a transient phase, the error profile exhibits a "solitonic behavior". Namely, a uniquely-shaped wavelike solution develops, that propagates with constant velocity. Read More

In this paper, we propose a generalized expectation consistent signal recovery algorithm to estimate the signal $\mathbf{x}$ from the nonlinear measurements of a linear transform output $\mathbf{z}=\mathbf{A}\mathbf{x}$. This estimation problem has been encountered in many applications, such as communications with front-end impairments, compressed sensing, and phase retrieval. The proposed algorithm extends the prior art called generalized turbo signal recovery from a partial discrete Fourier transform matrix $\mathbf{A}$ to a class of general matrices. Read More

We consider the design of wireless queueing network control policies with particular focus on combining stability with additional application-dependent requirements. Thereby, we consequently pursue a cost function based approach that provides the flexibility to incorporate constraints and requirements of particular services or applications. As typical examples of such requirements, we consider the reduction of buffer underflows in case of streaming traffic, and energy efficiency in networks of battery powered nodes. Read More

Feedback control actively dissipates uncertainty from a dynamical system by means of actuation. We develop a notion of "control capacity" that gives a fundamental limit (in bits) on the rate at which a controller can dissipate the uncertainty from a system, i.e. Read More

A secret sharing scheme (SSS) was introduced by Shamir in 1979 using polynomial interpolation. Later it turned out that it is equivalent to an SSS based on a Reed-Solomon code. SSSs based on linear codes have been studied by many researchers. Read More