Source author record

Venkat Chandar

Venkat Chandar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT Data Structures and Algorithms

Catalog footprint

What is connected

8works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

$O(\log \log n)$ Worst-Case Local Decoding and Update Efficiency for Data Compression

This paper addresses the problem of data compression with local decoding and local update. A compression scheme has worst-case local decoding $d_{wc}$ if any bit of the raw file can be recovered by probing at most $d_{wc}$ bits of the compressed sequence, and has update efficiency of $u_{wc}$ if a single bit of the raw file can be updated by modifying at most $u_{wc}$ bits of the compressed sequence. This article provides an entropy-achieving compression scheme for memoryless sources that simultaneously achieves $ O(\log\log n) $ local decoding and update efficiency. Key to this achievability result is a novel succinct data structure for sparse sequences which allows efficient local decoding and local update. Under general assumptions on the local decoder and update algorithms, a converse result shows that $d_{wc}$ and $u_{wc}$ must grow as $ Ω(\log\log n) $.

preprint2013arXiv

Energy and Sampling Constrained Asynchronous Communication

The minimum energy, and, more generally, the minimum cost, to transmit one bit of information has been recently derived for bursty communication when information is available infrequently at random times at the transmitter. This result assumes that the receiver is always in the listening mode and samples all channel outputs until it makes a decision. If the receiver is constrained to sample only a fraction f>0 of the channel outputs, what is the cost penalty due to sparse output sampling? Remarkably, there is no penalty: regardless of f>0 the asynchronous capacity per unit cost is the same as under full sampling, ie, when f=1. There is not even a penalty in terms of decoding delay---the elapsed time between when information is available until when it is decoded. This latter result relies on the possibility to sample adaptively; the next sample can be chosen as a function of past samples. Under non-adaptive sampling, it is possible to achieve the full sampling asynchronous capacity per unit cost, but the decoding delay gets multiplied by 1/f. Therefore adaptive sampling strategies are of particular interest in the very sparse sampling regime.

preprint2013arXiv

Update-Efficiency and Local Repairability Limits for Capacity Approaching Codes

Motivated by distributed storage applications, we investigate the degree to which capacity achieving encodings can be efficiently updated when a single information bit changes, and the degree to which such encodings can be efficiently (i.e., locally) repaired when single encoded bit is lost. Specifically, we first develop conditions under which optimum error-correction and update-efficiency are possible, and establish that the number of encoded bits that must change in response to a change in a single information bit must scale logarithmically in the block-length of the code if we are to achieve any nontrivial rate with vanishing probability of error over the binary erasure or binary symmetric channels. Moreover, we show there exist capacity-achieving codes with this scaling. With respect to local repairability, we develop tight upper and lower bounds on the number of remaining encoded bits that are needed to recover a single lost bit of the encoding. In particular, we show that if the code-rate is $ε$ less than the capacity, then for optimal codes, the maximum number of codeword symbols required to recover one lost symbol must scale as $\log1/ε$. Several variations on---and extensions of---these results are also developed.

preprint2012arXiv

Asynchronous Capacity per Unit Cost

The capacity per unit cost, or equivalently minimum cost to transmit one bit, is a well-studied quantity. It has been studied under the assumption of full synchrony between the transmitter and the receiver. In many applications, such as sensor networks, transmissions are very bursty, with small amounts of bits arriving infrequently at random times. In such scenarios, the cost of acquiring synchronization is significant and one is interested in the fundamental limits on communication without assuming a priori synchronization. In this paper, we show that the minimum cost to transmit B bits of information asynchronously is (B + \bar{H})k_sync, where k_sync is the synchronous minimum cost per bit and \bar{H} is a measure of timing uncertainty equal to the entropy for most reasonable arrival time distributions. This result holds when the transmitter can stay idle at no cost and is a particular case of a general result which holds for arbitrary cost functions.

preprint2012arXiv

Asynchronous Communication: Capacity Bounds and Suboptimality of Training

Several aspects of the problem of asynchronous point-to-point communication without feedback are developed when the source is highly intermittent. In the system model of interest, the codeword is transmitted at a random time within a prescribed window whose length corresponds to the level of asynchronism between the transmitter and the receiver. The decoder operates sequentially and communication rate is defined as the ratio between the message size and the elapsed time between when transmission commences and when the decoder makes a decision. For such systems, general upper and lower bounds on capacity as a function of the level of asynchronism are established, and are shown to coincide in some nontrivial cases. From these bounds, several properties of this asynchronous capacity are derived. In addition, the performance of training-based schemes is investigated. It is shown that such schemes, which implement synchronization and information transmission on separate degrees of freedom in the encoding, cannot achieve the asynchronous capacity in general, and that the penalty is particularly significant in the high-rate regime.

preprint2010arXiv

A Simple Message-Passing Algorithm for Compressed Sensing

We consider the recovery of a nonnegative vector x from measurements y = Ax, where A is an m-by-n matrix whos entries are in {0, 1}. We establish that when A corresponds to the adjacency matrix of a bipartite graph with sufficient expansion, a simple message-passing algorithm produces an estimate \hat{x} of x satisfying ||x-\hat{x}||_1 \leq O(n/k) ||x-x(k)||_1, where x(k) is the best k-sparse approximation of x. The algorithm performs O(n (log(n/k))^2 log(k)) computation in total, and the number of measurements required is m = O(k log(n/k)). In the special case when x is k-sparse, the algorithm recovers x exactly in time O(n log(n/k) log(k)). Ultimately, this work is a further step in the direction of more formally developing the broader role of message-passing algorithms in solving compressed sensing problems.

preprint2010arXiv

On Bounded Weight Codes

The maximum size of a binary code is studied as a function of its length N, minimum distance D, and minimum codeword weight W. This function B(N,D,W) is first characterized in terms of its exponential growth rate in the limit as N tends to infinity for fixed d=D/N and w=W/N. The exponential growth rate of B(N,D,W) is shown to be equal to the exponential growth rate of A(N,D) for w <= 1/2, and equal to the exponential growth rate of A(N,D,W) for 1/2< w <= 1. Second, analytic and numerical upper bounds on B(N,D,W) are derived using the semidefinite programming (SDP) method. These bounds yield a non-asymptotic improvement of the second Johnson bound and are tight for certain values of the parameters.

preprint2009arXiv

Training-Based Schemes are Suboptimal for High Rate Asynchronous Communication

We consider asynchronous point-to-point communication. Building on a recently developed model, we show that training based schemes, i.e., communication strategies that separate synchronization from information transmission, perform suboptimally at high rate.