BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ashish Khisti

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

ResearcherUnclaimed source record
Information Theorymath.ITMachine LearningCryptography and SecurityNetworking and Internet ArchitectureApplicationseess.IVMultimediaNeurons and Cognition

Catalog footprint

What is connected

39works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

39 published item(s)

preprint2026arXiv

List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression

We study a relaxation of the problem of coupling probability distributions -- a list of samples is generated from one distribution and an accept is declared if any one of these samples is identical to the sample generated from the other distribution. We propose a novel method for generating samples, which extends the Gumbel-max sampling suggested in Daliri et al. (arXiv:2408.07978) for coupling probability distributions. We also establish a corresponding lower bound on the acceptance probability, which we call the list matching lemma. We next discuss two applications of our setup. First, we develop a new mechanism for multi-draft speculative sampling that is simple to implement and achieves performance competitive with baselines such as SpecTr and SpecInfer across a range of language tasks. Our method also guarantees a certain degree of drafter invariance with respect to the output tokens which is not supported by existing schemes. We also provide a theoretical lower bound on the token level acceptance probability. As our second application, we consider distributed lossy compression with side information in a setting where a source sample is compressed and available to multiple decoders, each with independent side information. We propose a compression technique that is based on our generalization of Gumbel-max sampling and show that it provides significant gains in experiments involving synthetic Gaussian sources and the MNIST image dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Adaptive relaying for streaming erasure codes in a three node relay network

This paper investigates adaptive streaming codes over a three-node relayed network. In this setting, a source node transmits a sequence of message packets to a destination through a relay. The source-to-relay and relay-to-destination links are unreliable and introduce at most $N_1$ and $N_2$ packet erasures, respectively. The destination node must recover each message packet within a strict delay constraint $T$. The paper presents achievable streaming codes for all feasible parameters $\{N_1, N_2, T\}$ that exploit the fact that the relay naturally observes the erasure pattern occurring in the link from source to relay, thus it can adapt its relaying strategy based on these observations. In a recent work, Fong et al. provide streaming codes featuring channel-state-independent relaying strategies. The codes proposed in this paper achieve rates higher than the ones proposed by Fong et al. whenever $N_2 > N_1$, and achieve the same rate when $N_2 = N_1$. The paper also presents an upper bound on the achievable rate that takes into account erasures in both links in order to bound the rate in the second link. The upper bound is shown to be tighter than a trivial bound that considers only the erasures in the second link.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Error-correcting codes for low latency streaming over multiple link relay networks

This paper investigates the performance of streaming codes in low-latency applications over a multi-link three-node relayed network. The source wishes to transmit a sequence of messages to the destination through a relay. Each message must be reconstructed after a fixed decoding delay. The special case with one link connecting each node has been studied by Fong et. al [1], and a multi-hop multi-link setting has been studied by Domanovitz et. al [2]. The topology with three nodes and multiple links is studied in this paper. Each link is subject to a different number of erasures due to different channel conditions. An information-theoretic upper bound is derived, and an achievable scheme is presented. The proposed scheme judiciously allocates rates for each link based on the concept of delay spectrum. The achievable scheme is compared to two baseline schemes and the scheme proposed in [2]. Experimental results show that this scheme achieves higher rates than the other schemes, and can achieve the upper bound even in non-trivial scenarios. The scheme is further extended to handle different propagation delays in each link, something not previously considered in the literature. Simulations over statistical channels show that the proposed scheme can outperform the simpler baseline under practical models.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Streaming Erasure Codes over the Three-Node Relay Network

This paper investigates low-latency streaming codes for a three-node relay network. The source transmits a sequence of messages (streaming messages) to the destination through the relay between them, where the first-hop channel from the source to the relay and the second-hop channel from the relay to the destination are subject to packet erasures. Every source message must be recovered perfectly at the destination subject to a fixed decoding delay of $T$ time slots. In any sliding window of $T+1$ time slots, we assume no more than $N_1$ and $N_2$ erasures are introduced by the first-hop channel and second-hop channel respectively. Under this channel loss assumption, we fully characterize the maximum achievable rate in terms of $T$, $N_1$ and $N_2$. The achievability is proved by using a symbol-wise decode-forward strategy where the source symbols within the same message are decoded by the relay with different delays. The converse is proved by analyzing the maximum achievable rate for each channel when the erasures in the other channel are consecutive (bursty). In addition, we show that traditional message-wise decode-forward strategies, which require the source symbols within the same message to be decoded by the relay with the same delay, are sub-optimal in general.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Variational Model Inversion Attacks

Given the ubiquity of deep neural networks, it is important that these models do not reveal information about sensitive data that they have been trained on. In model inversion attacks, a malicious user attempts to recover the private dataset used to train a supervised neural network. A successful model inversion attack should generate realistic and diverse samples that accurately describe each of the classes in the private dataset. In this work, we provide a probabilistic interpretation of model inversion attacks, and formulate a variational objective that accounts for both diversity and accuracy. In order to optimize this variational objective, we choose a variational family defined in the code space of a deep generative model, trained on a public auxiliary dataset that shares some structural similarity with the target dataset. Empirically, our method substantially improves performance in terms of target attack accuracy, sample realism, and diversity on datasets of faces and chest X-ray images.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Sequential Classification with Empirically Observed Statistics

Motivated by real-world machine learning applications, we consider a statistical classification task in a sequential setting where test samples arrive sequentially. In addition, the generating distributions are unknown and only a set of empirically sampled sequences are available to a decision maker. The decision maker is tasked to classify a test sequence which is known to be generated according to either one of the distributions. In particular, for the binary case, the decision maker wishes to perform the classification task with minimum number of the test samples, so, at each step, she declares that either hypothesis 1 is true, hypothesis 2 is true, or she requests for an additional test sample. We propose a classifier and analyze the type-I and type-II error probabilities. We demonstrate the significant advantage of our sequential scheme compared to an existing non-sequential classifier proposed by Gutman. Finally, we extend our setup and results to the multi-class classification scenario and again demonstrate that the variable-length nature of the problem affords significant advantages as one can achieve the same set of exponents as Gutman's fixed-length setting but without having the rejection option.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Explicit Rate-Optimal Streaming Code for Channels with Burst and Arbitrary Erasures

This paper considers the transmission of an infinite sequence of messages (a streaming source) over a packet erasure channel, where every source message must be recovered perfectly at the destination subject to a fixed decoding delay. While the capacity of a channel that introduces only bursts of erasures is well known, only recently, the capacity of a channel with either one burst of erasures or multiple arbitrary erasures in any fixed-sized sliding window has been established. However, the codes shown to achieve this capacity are either non-explicit constructions (proven to exist) or explicit constructions that require large field size that scales exponentially with the delay. This work describes an explicit rate-optimal construction for admissible channel and delay parameters over a field size that scales only quadratically with the delay.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates

In this work, we improve upon the stepwise analysis of noisy iterative learning algorithms initiated by Pensia, Jog, and Loh (2018) and recently extended by Bu, Zou, and Veeravalli (2019). Our main contributions are significantly improved mutual information bounds for Stochastic Gradient Langevin Dynamics via data-dependent estimates. Our approach is based on the variational characterization of mutual information and the use of data-dependent priors that forecast the mini-batch gradient based on a subset of the training samples. Our approach is broadly applicable within the information-theoretic framework of Russo and Zou (2015) and Xu and Raginsky (2017). Our bound can be tied to a measure of flatness of the empirical risk surface. As compared with other bounds that depend on the squared norms of gradients, empirical investigations show that the terms in our bounds are orders of magnitude smaller.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Low-Latency Network-Adaptive Error Control for Interactive Streaming

We introduce a novel network-adaptive algorithm that is suitable for alleviating network packet losses for low-latency interactive communications between a source and a destination. Our network-adaptive algorithm estimates in real-time the best parameters of a recently proposed streaming code that uses forward error correction (FEC) to correct both arbitrary and burst losses, which cause a crackling noise and undesirable jitters, respectively in audio. In particular, the destination estimates appropriate coding parameters based on its observed packet loss pattern and sends them back to the source for updating the underlying code. Besides, a new explicit construction of practical low-latency streaming codes that achieve the optimal tradeoff between the capability of correcting arbitrary losses and the capability of correcting burst losses is provided. Simulation evaluations based on statistical losses and real-world packet loss traces reveal the following: (i) Our proposed network-adaptive algorithm combined with our optimal streaming codes can achieve significantly higher performance compared to uncoded and non-adaptive FEC schemes over UDP (User Datagram Protocol); (ii) Our explicit streaming codes can significantly outperform traditional MDS (maximum-distance separable) streaming schemes when they are used along with our network-adaptive algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Streaming Erasure Codes over Multi-hop Relay Network

This paper studies low-latency streaming codes for the multi-hop network. The source is transmitting a sequence of messages (streaming messages) to a destination through a chain of relays where each hop is subject to packet erasures. Every source message has to be recovered perfectly at the destination within a delay constraint of $T$ time slots. In any sliding window of $T+1$ time slots, we assume no more than $N_j$ erasures introduced by the $j$'th hop channel. The capacity in case of a single relay (a three-node network) was derived by Fong [1], et al. While the converse derived for the three-node case can be extended to any number of nodes using a similar technique (analyzing the case where erasures on other links are consecutive), we demonstrate next that the achievable scheme, which suggested a clever symbol-wise decode and forward strategy, can not be straightforwardly extended without a loss in performance. The coding scheme for the three-node network, which was shown to achieve the upper bound, was ``state-independent'' (i.e., it does not depend on specific erasure pattern). While this is a very desirable property, in this paper, we suggest a ``state-dependent'' (i.e., a scheme which depends on specific erasure pattern) and show that it achieves the upper bound up to the size of an additional header. Since, as we show, the size of the header does not depend on the field size, the gap between the achievable rate and the upper bound decreases as the field size increases.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Time-Resolved fMRI Shared Response Model using Gaussian Process Factor Analysis

Multi-subject fMRI studies are challenging due to the high variability of both brain anatomy and functional brain topographies across participants. An effective way of aggregating multi-subject fMRI data is to extract a shared representation that filters out unwanted variability among subjects. Some recent work has implemented probabilistic models to extract a shared representation in task fMRI. In the present work, we improve upon these models by incorporating temporal information in the common latent structures. We introduce a new model, Shared Gaussian Process Factor Analysis (S-GPFA), that discovers shared latent trajectories and subject-specific functional topographies, while modelling temporal correlation in fMRI data. We demonstrate the efficacy of our model in revealing ground truth latent structures using simulated data, and replicate experimental performance of time-segment matching and inter-subject similarity on the publicly available Raider and Sherlock datasets. We further test the utility of our model by analyzing its learned model parameters in the large multi-site SPINS dataset, on a social cognition task from participants with and without schizophrenia.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convolutional Codes with Maximum Column Sum Rank for Network Streaming

The column Hamming distance of a convolutional code determines the error correction capability when streaming over a class of packet erasure channels. We introduce a metric known as the column sum rank, that parallels column Hamming distance when streaming over a network with link failures. We prove rank analogues of several known column Hamming distance properties and introduce a new family of convolutional codes that maximize the column sum rank up to the code memory. Our construction involves finding a class of super-regular matrices that preserve this property after multiplication with non-singular block diagonal matrices in the ground field.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Exact Moderate Deviation Asymptotics in Streaming Data Transmission

In this paper, a streaming transmission setup is considered where an encoder observes a new message in the beginning of each block and a decoder sequentially decodes each message after a delay of $T$ blocks. In this streaming setup, the fundamental interplay between the coding rate, the error probability, and the blocklength in the moderate deviations regime is studied. For output symmetric channels, the moderate deviations constant is shown to improve over the block coding or non-streaming setup by exactly a factor of $T$ for a certain range of moderate deviations scalings. For the converse proof, a more powerful decoder to which some extra information is fedforward is assumed. The error probability is bounded first for an auxiliary channel and this result is translated back to the original channel by using a newly developed change-of-measure lemma, where the speed of decay of the remainder term in the exponent is carefully characterized. For the achievability proof, a known coding technique that involves a joint encoding and decoding of fresh and past messages is applied with some manipulations in the error analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The MIMO Wiretap Channel Decomposed

The problem of sending a secret message over the Gaussian multiple-input multiple-output (MIMO) wiretap channel is studied. While the capacity of this channel is known, it is not clear how to construct optimal coding schemes that achieve this capacity. In this work, we use linear operations along with successive interference cancellation to attain effective parallel single-antenna wiretap channels. By using independent scalar Gaussian wiretap codebooks over the resulting parallel channels, the capacity of the MIMO wiretap channel is achieved. The derivation of the schemes is based upon joint triangularization of the channel matrices. We find that the same technique can be used to re-derive capacity expressions for the MIMO wiretap channel in a way that is simple and closely connected to a transmission scheme. This technique allows to extend the previously proven strong security for scalar Gaussian channels to the MIMO case. We further consider the problem of transmitting confidential messages over a two-user broadcast MIMO channel. For that problem, we find that derivation of both the capacity and a transmission scheme is a direct corollary of the proposed analysis for the MIMO wiretap channel.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Wiretapped Diamond-Relay Channel

In this paper, we study a diamond-relay channel where the source is connected to $M$ relays through orthogonal links and the relays transmit to the destination over a wireless multiple-access channel in the presence of an eavesdropper. The eavesdropper not only observes the relay transmissions through another multiple-access channel, but also observes a certain number of source-relay links. The legitimate terminals know neither the eavesdropper's channel state information nor the location of source-relay links revealed to the eavesdropper except the total number of such links. For this wiretapped diamond-relay channel, we establish the optimal secure degrees of freedom. In the achievability part, our proposed scheme uses the source-relay links to transmit a judiciously constructed combination of message symbols, artificial noise symbols as well as fictitious message symbols associated with secure network coding. The relays use a combination of beamforming and interference alignment in their transmission scheme. For the converse part, we take a genie-aided approach assuming that the location of wiretapped links is known.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Secure Degrees of Freedom of the Gaussian Diamond-Wiretap Channel

In this paper, we consider the Gaussian diamond-wiretap channel that consists of an orthogonal broadcast channel from a source to two relays and a Gaussian fast-fading multiple access-wiretap channel from the two relays to a legitimate destination and an eavesdropper. For the multiple access part, we consider both the case with full channel state information (CSI) and the case with no eavesdropper's CSI, at the relays and the legitimate destination. For both the cases, we establish the exact secure degrees of freedom and generalize the results for multiple relays. For the converse part, we introduce a new technique of capturing the trade-off between the message rate and the amount of individual randomness injected at each relay. In the achievability part, we show (i) how to strike a balance between sending message symbols and common noise symbols from the source to the relays in the broadcast component and (ii) how to combine artificial noise-beamforming and noise-alignment techniques at the relays in the multiple access component. In the case with full CSI, we propose a scheme where the relays simultaneously beamform common noise signals in the null space of the legitimate destination's channel, and align them with the message signals at the eavesdropper. In the case with no eavesdropper's CSI, we present a scheme that efficiently utilizes the broadcast links by incorporating computation between the message and common noise symbols at the source. Finally, most of our achievability and converse techniques can also be adapted to the Gaussian (non-fading) channel model.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Streaming Data Transmission in the Moderate Deviations and Central Limit Regimes

We consider streaming data transmission over a discrete memoryless channel. A new message is given to the encoder at the beginning of each block and the decoder decodes each message sequentially, after a delay of $T$ blocks. In this streaming setup, we study the fundamental interplay between the rate and error probability in the central limit and moderate deviations regimes and show that i) in the moderate deviations regime, the moderate deviations constant improves over the block coding or non-streaming setup by a factor of $T$ and ii) in the central limit regime, the second-order coding rate improves by a factor of approximately $\sqrt{T}$ for a wide range of channel parameters. For both regimes, we propose coding techniques that incorporate a joint encoding of fresh and previous messages. In particular, for the central limit regime, we propose a coding technique with truncated memory to ensure that a summation of constants, which arises as a result of applications of the central limit theorem, does not diverge in the error analysis. Furthermore, we explore interesting variants of the basic streaming setup in the moderate deviations regime. We first consider a scenario with an erasure option at the decoder and show that both the exponents of the total error and the undetected error probabilities improve by factors of $T$. Next, by utilizing the erasure option, we show that the exponent of the total error probability can be improved to that of the undetected error probability (in the order sense) at the expense of a variable decoding delay. Finally, we also extend our results to the case where the message rate is not fixed but alternates between two values.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Degraded Gaussian Diamond-Wiretap Channel

In this paper, we present nontrivial upper and lower bounds on the secrecy capacity of the degraded Gaussian diamond-wiretap channel and identify several ranges of channel parameters where these bounds coincide with useful intuitions. Furthermore, we investigate the effect of the presence of an eavesdropper on the capacity. We consider the following two scenarios regarding the availability of randomness: 1) a common randomness is available at the source and the two relays and 2) a randomness is available only at the source and there is no available randomness at the relays. We obtain the upper bound by taking into account the correlation between the two relay signals and the availability of randomness at each encoder. For the lower bound, we propose two types of coding schemes: 1) a decode-and-forward scheme where the relays cooperatively transmit the message and the fictitious message and 2) a partial DF scheme incorporated with multicoding in which each relay sends an independent partial message and the whole or partial fictitious message using dependent codewords.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parallel Gaussian Networks with a Common State-Cognitive Helper

A class of state-dependent parallel networks with a common state-cognitive helper, in which $K$ transmitters wish to send $K$ messages to their corresponding receivers over $K$ state-corrupted parallel channels, and a helper who knows the state information noncausally wishes to assist these receivers to cancel state interference. Furthermore, the helper also has its own message to be sent simultaneously to its corresponding receiver. Since the state information is known only to the helper, but not to the corresponding transmitters $1,\dots,K$, transmitter-side state cognition and receiver-side state interference are mismatched. Our focus is on the high state power regime, i.e., the state power goes to infinity. Three (sub)models are studied. Model I serves as a basic model, which consists of only one transmitter-receiver (with state corruption) pair in addition to a helper that assists the receiver to cancel state in addition to transmitting its own message. Model II consists of two transmitter-receiver pairs in addition to a helper, and only one receiver is interfered by a state sequence. Model III generalizes model I include multiple transmitter-receiver pairs with each receiver corrupted by independent state. For all models, inner and outer bounds on the capacity region are derived, and comparison of the two bounds leads to characterization of either full or partial boundary of the capacity region under various channel parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Streaming-DMT of Fading Channels

We consider the sequential transmission of a stream of messages over a block-fading multi-input-multi-output (MIMO) channel. A new message arrives at the beginning of each coherence block, and the decoder is required to output each message sequentially, after a delay of $T$ coherence blocks. In the special case when $T=1$, the setup reduces to the quasi-static fading channel. We establish the optimal diversity-multiplexing tradeoff (DMT) in the high signal-to-noise-ratio (SNR) regime, and show that it equals $T$ times the DMT of the quasi-static channel. The converse is based on utilizing the delay constraint to amplify a local outage event associated with a message, globally across all the coherence blocks. This approach appears to be new. We propose two coding schemes that achieve the optimal DMT. The first scheme involves interleaving of messages, such that each message is transmitted across $T$ consecutive coherence blocks. This scheme requires the knowledge of the delay constraint at both the encoder and decoder. Our second coding scheme involves a sequential tree code and is delay-universal i.e., the knowledge of the decoding delay is not required by the encoder. However, in this scheme we require the coherence block-length to increase as $\log\mathrm{({SNR})}$, in order to attain the optimal DMT. Finally, we discuss the case when multiple messages arrive at uniform intervals {\em within} each coherence period. Through a simple example we exhibit the sub-optimality of interleaving, and propose another scheme that achieves the optimal DMT.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Zero-Delay Sequential Transmission of Markov Sources Over Burst Erasure Channels

A setup involving zero-delay sequential transmission of a vector Markov source over a burst erasure channel is studied. A sequence of source vectors is compressed in a causal fashion at the encoder, and the resulting output is transmitted over a burst erasure channel. The destination is required to reconstruct each source vector with zero-delay, but those source sequences that are observed either during the burst erasure, or in the interval of length $W$ following the burst erasure need not be reconstructed. The minimum achievable compression rate is called the rate-recovery function. We assume that each source vector is sampled i.i.d. across the spatial dimension and from a stationary, first-order Markov process across the temporal dimension. For discrete sources the case of lossless recovery is considered, and upper and lower bounds on the rate-recovery function are established. Both these bounds can be expressed as the rate for predictive coding, plus a term that decreases at least inversely with the recovery window length $W$. For Gauss-Markov sources and a quadratic distortion measure, upper and lower bounds on the minimum rate are established when $W=0$. These bounds are shown to coincide in the high resolution limit. Finally another setup involving i.i.d. Gaussian sources is studied and the rate-recovery function is completely characterized in this case.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Layered Constructions for Low-Delay Streaming Codes

We propose a new class of error correction codes for low-delay streaming communication. We consider an online setup where a source packet arrives at the encoder every $M$ channel uses, and needs to be decoded with a maximum delay of $T$ packets. We consider a sliding-window erasure channel --- $\cC(N,B,W)$ --- which introduces either up to $N$ erasures in arbitrary positions, or $B$ erasures in a single burst, in any window of length $W$. When $M=1$, the case where source-arrival and channel-transmission rates are equal, we propose a class of codes --- MiDAS codes --- that achieve a near optimal rate. Our construction is based on a {\em layered} approach. We first construct an optimal code for the $\cC(N=1,B,W)$ channel, and then concatenate an additional layer of parity-check symbols to deal with $N>1$. When $M > 1$, the case where source-arrival and channel-transmission rates are unequal, we characterize the capacity when $N=1$ and $W \ge M(T+1),$ and for $N>1$, we propose a construction based on a layered approach. Numerical simulations over Gilbert-Elliott and Fritchman channel models indicate significant gains in the residual loss probability over baseline schemes. We also discuss the connection between the error correction properties of the MiDAS codes and their underlying column distance and column span.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

MIMO Broadcast Channel with an Unknown Eavesdropper: Secrecy Degrees of Freedom

We study a multi-antenna broadcast channel with two legitimate receivers and an external eavesdropper. We assume that the channel matrix of the eavesdropper is unknown to the legitimate terminals but satisfies a maximum rank constraint. As our main result we characterize the associated secrecy degrees of freedom for the broadcast channel with common and private messages. We show that a direct extension of the single-user wiretap codebook does not achieve the secrecy degrees of freedom. Our proposed optimal scheme involves decomposing the signal space into a common subspace, which can be observed by both receivers, and private subspaces which can be observed by only one of the receivers, and carefully transmitting a subset of messages in each subspace. We also consider the case when each user's private message must additionally remain confidential from the other legitimate receiver and characterize the s.d.o.f.\ region in this case.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Robust Streaming Erasure Codes based on Deterministic Channel Approximations

We study near optimal error correction codes for real-time communication. In our setup the encoder must operate on an incoming source stream in a sequential manner, and the decoder must reconstruct each source packet within a fixed playback deadline of $T$ packets. The underlying channel is a packet erasure channel that can introduce both burst and isolated losses. We first consider a class of channels that in any window of length ${T+1}$ introduce either a single erasure burst of a given maximum length $B,$ or a certain maximum number $N$ of isolated erasures. We demonstrate that for a fixed rate and delay, there exists a tradeoff between the achievable values of $B$ and $N,$ and propose a family of codes that is near optimal with respect to this tradeoff. We also consider another class of channels that introduce both a burst {\em and} an isolated loss in each window of interest and develop the associated streaming codes. All our constructions are based on a layered design and provide significant improvements over baseline codes in simulations over the Gilbert-Elliott channel.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Streaming-Codes for Multicast over Burst Erasure Channels

We study the capacity limits of real-time streaming over burst-erasure channels. A stream of source packets must be sequentially encoded and the resulting channel packets must be transmitted over a two-receiver burst-erasure broadcast channel. The source packets must be sequentially reconstructed at each receiver with a possibly different reconstruction deadline. We study the associated capacity as a function of burst-lengths and delays at the two receivers. We establish that the operation of the system can be divided into two main regimes: a low-delay regime and a large-delay regime. We fully characterize the capacity in the large delay regime. The key to this characterization is an inherent slackness in the delay of one of the receivers. At every point in this regime we can reduce the delay of at-least one of the users until a certain critical value and thus it suffices to obtain code constructions for certain critical delays. We partially characterize the capacity in the low-delay regime. Our capacity results involve code constructions and converse techniques that appear to be novel. We also provide a rigorous information theoretic converse theorem in the point-to-point setting which was studied by Martinian in an earlier work.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

MIMO Multiple Access Channel with an Arbitrarily Varying Eavesdropper

A two-transmitter Gaussian multiple access wiretap channel with multiple antennas at each of the nodes is investigated. The channel matrices at the legitimate terminals are fixed and revealed to all the terminals, whereas the channel matrix of the eavesdropper is arbitrarily varying and only known to the eavesdropper. The secrecy degrees of freedom (s.d.o.f.) region under a strong secrecy constraint is characterized. A transmission scheme that orthogonalizes the transmit signals of the two users at the intended receiver and uses a single-user wiretap code is shown to be sufficient to achieve the s.d.o.f. region. The converse involves establishing an upper bound on a weighted-sum-rate expression. This is accomplished by using induction, where at each step one combines the secrecy and multiple-access constraints associated with an adversary eavesdropping a carefully selected group of sub-channels.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Modulo-Sum Computation over an Erasure Multiple Access Channel

We study computation of a modulo-sum of two binary source sequences over a two-user erasure multiple access channel. The channel is modeled as a binary-input, erasure multiple access channel, which can be in one of three states - either the channel output is a modulo-sum of the two input symbols, or the channel output equals the input symbol on the first link and an erasure on the second link, or vice versa. The associated state sequence is independent and identically distributed. We develop a new upper bound on the sum-rate by revealing only part of the state sequence to the transmitters. Our coding scheme is based on the compute and forward and the decode and forward techniques. When a (strictly) causal feedback of the channel state is available to the encoders, we show that the modulo-sum capacity is increased. Extensions to the case of lossy reconstruction of the modulo-sum and to channels involving additional states are also treated briefly.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Private Broadcasting over Independent Parallel Channels

We study private broadcasting of two messages to two groups of receivers over independent parallel channels. One group consists of an arbitrary number of receivers interested in a common message, whereas the other group has only one receiver. Each message must be kept confidential from the receiver(s) in the other group. Each of the sub-channels is degraded, but the order of receivers on each channel can be different. While corner points of the capacity region were characterized in earlier works, we establish the capacity region and show the optimality of a superposition strategy. For the case of parallel Gaussian channels, we show that a Gaussian input distribution is optimal. We also discuss an extension of our setup to broadcasting over a block-fading channel and demonstrate significant performance gains using the proposed scheme over a baseline time-sharing scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Secret-Key Agreement Capacity over Reciprocal Fading Channels: A Separation Approach

Fundamental limits of secret-key agreement over reciprocal wireless channels are investigated. We consider a two-way block-fading channel where the channel gains in the forward and reverse links between the legitimate terminals are correlated. The channel gains between the legitimate terminals are not revealed to any terminal, whereas the channel gains of the eavesdropper are revealed to the eavesdropper. We propose a two-phase transmission scheme, that reserves a certain portion of each coherence block for channel estimation, and the remainder of the coherence block for correlated source generation. The resulting secret-key involves contributions of both channel sequences and source sequences, with the contribution of the latter becoming dominant as the coherence period increases. We also establish an upper bound on the secret-key capacity, which has a form structurally similar to the lower bound. Our upper and lower bounds coincide in the limit of high signal-to-noise-ratio (SNR) and large coherence period, thus establishing the secret-key agreement capacity in this asymptotic regime. Numerical results indicate that the proposed scheme achieves significant gains over training-only schemes, even for moderate SNR and small coherence periods, thus implying the necessity of randomness-sharing in practical secret-key generation systems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sequential Coding of Markov Sources over Burst Erasure Channels

We study sequential coding of Markov sources under an error propagation constraint. An encoder sequentially compresses a sequence of vector-sources that are spatially i.i.d. but temporally correlated according to a first-order Markov process. The channel erases up to B packets in a single burst, but reveals all other packets to the destination. The destination is required to reproduce all the source-vectors instantaneously and in a lossless manner, except those sequences that occur in an error propagation window of length B + W following the start of the erasure burst. We define the rate-recovery function R(B, W) - the minimum achievable compression rate per source sample in this framework - and develop upper and lower bounds on this function. Our upper bound is obtained using a random binning technique, whereas our lower bound is obtained by drawing connections to multi-terminal source coding. Our upper and lower bounds coincide, yielding R(B, W), in some special cases. More generally, both the upper and lower bounds equal the rate for predictive coding plus a term that decreases as 1/(W+1), thus establishing a scaling behaviour of the rate-recovery function. For a special class of semi-deterministic Markov sources we propose a new optimal coding scheme: prospicient coding. An extension of this coding technique to Gaussian sources is also developed. For the class of symmetric Markov sources and memoryless encoders, we establish the optimality of random binning. When the destination is required to reproduce each source sequence with a fixed delay and when W = 0 we also establish the optimality of binning.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Streaming Codes for Channels with Burst and Isolated Erasures

We study low-delay error correction codes for streaming recovery over a class of packet-erasure channels that introduce both burst-erasures and isolated erasures. We propose a simple, yet effective class of codes whose parameters can be tuned to obtain a tradeoff between the capability to correct burst and isolated erasures. Our construction generalizes previously proposed low-delay codes which are effective only against burst erasures. We establish an information theoretic upper bound on the capability of any code to simultaneously correct burst and isolated erasures and show that our proposed constructions meet the upper bound in some special cases. We discuss the operational significance of column-distance and column-span metrics and establish that the rate 1/2 codes discovered by Martinian and Sundberg [IT Trans.\, 2004] through a computer search indeed attain the optimal column-distance and column-span tradeoff. Numerical simulations over a Gilbert-Elliott channel model and a Fritchman model show significant performance gains over previously proposed low-delay codes and random linear codes for certain range of channel parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Diversity Embedded Streaming Erasure Codes (DE-SCo): Constructions and Optimality

Streaming erasure codes guarantee that each source packet is recovered within a fixed delay at the receiver over a burst-erasure channel. This paper introduces a new class of streaming codes: Diversity Embedded Streaming Erasure Codes (DE-SCo), that provide a flexible tradeoff between the channel quality and receiver delay. When the channel conditions are good, the source stream is recovered with a low delay, whereas when the channel conditions are poor the source stream is still recovered, albeit with a larger delay. Information theoretic analysis of the underlying burst-erasure broadcast channel reveals that DE-SCo achieve the minimum possible delay for the weaker user, without sacrificing the single-user optimal performance of the stronger user. Our constructions are explicit, incur polynomial time encoding and decoding complexity and outperform random linear codes over burst-erasure channels.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Diversity Embedded Streaming Erasure Codes (DE-SCo): Constructions and Optimality

Streaming erasure codes encode a source stream to guarantee that each source packet is recovered within a fixed delay at the receiver over a burst-erasure channel. This paper introduces diversity embedded streaming erasure codes (DE-SCo), that provide a flexible tradeoff between the channel quality and receiver delay. When the channel conditions are good, the source stream is recovered with a low delay, whereas when the channel conditions are poor the source stream is still recovered, albeit with a larger delay. Information theoretic analysis of the underlying burst-erasure broadcast channel reveals that DE-SCo achieve the minimum possible delay for the weaker user, without sacrificing the performance of the stronger user. A larger class of multicast streaming erasure codes (MU-SCo) that achieve optimal tradeoff between rate, delay and erasure-burst length is also constructed.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Interference Alignment for the Multi-Antenna Compound Wiretap Channel

We study a wiretap channel model where the sender has $M$ transmit antennas and there are two groups consisting of $J_1$ and $J_2$ receivers respectively. Each receiver has a single antenna. We consider two scenarios. First we consider the compound wiretap model -- group 1 constitutes the set of legitimate receivers, all interested in a common message, whereas group 2 is the set of eavesdroppers. We establish new lower and upper bounds on the secure degrees of freedom. Our lower bound is based on the recently proposed \emph{real interference alignment} scheme. The upper bound provides the first known example which illustrates that the \emph{pairwise upper bound} used in earlier works is not tight. The second scenario we study is the compound private broadcast channel. Each group is interested in a message that must be protected from the other group. Upper and lower bounds on the degrees of freedom are developed by extending the results on the compound wiretap channel.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Secret key agreement on wiretap channels with transmitter side information

Secret-key agreement protocols over wiretap channels controlled by a state parameter are studied. The entire state sequence is known (non-causally) to the sender but not to the receiver and the eavesdropper. Upper and lower bounds on the secret-key capacity are established both with and without public discussion. The proposed coding scheme involves constructing a codebook to create common reconstruction of the state sequence at the sender and the receiver and another secret-key codebook constructed by random binning. For the special case of Gaussian channels, with no public discussion, - the secret-key generation with dirty paper problem, the gap between our bounds is at-most 1/2 bit and the bounds coincide in the high signal-to-noise ratio and high interference-to-noise ratio regimes. In the presence of public discussion our bounds coincide, yielding the capacity, when then the channels of the receiver and the eavesdropper satisfy an in- dependent noise condition.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Secret-key Agreement with Channel State Information at the Transmitter

We study the capacity of secret-key agreement over a wiretap channel with state parameters. The transmitter communicates to the legitimate receiver and the eavesdropper over a discrete memoryless wiretap channel with a memoryless state sequence. The transmitter and the legitimate receiver generate a shared secret key, that remains secret from the eavesdropper. No public discussion channel is available. The state sequence is known noncausally to the transmitter. We derive lower and upper bounds on the secret-key capacity. The lower bound involves constructing a common state reconstruction sequence at the legitimate terminals and binning the set of reconstruction sequences to obtain the secret-key. For the special case of Gaussian channels with additive interference (secret-keys from dirty paper channel) our bounds differ by 0.5 bit/symbol and coincide in the high signal-to-noise-ratio and high interference-to-noise-ratio regimes. For the case when the legitimate receiver is also revealed the state sequence, we establish that our lower bound achieves the the secret-key capacity. In addition, for this special case, we also propose another scheme that attains the capacity and requires only causal side information at the transmitter and the receiver.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Secure Transmission with Multiple Antennas II: The MIMOME Wiretap Channel

The capacity of the Gaussian wiretap channel model is analyzed when there are multiple antennas at the sender, intended receiver and eavesdropper. The associated channel matrices are fixed and known to all the terminals. A computable characterization of the secrecy capacity is established as the saddle point solution to a minimax problem. The converse is based on a Sato-type argument used in other broadcast settings, and the coding theorem is based on Gaussian wiretap codebooks. At high signal-to-noise ratio (SNR), the secrecy capacity is shown to be attained by simultaneously diagonalizing the channel matrices via the generalized singular value decomposition, and independently coding across the resulting parallel channels. The associated capacity is expressed in terms of the corresponding generalized singular values. It is shown that a semi-blind "masked" multi-input multi-output (MIMO) transmission strategy that sends information along directions in which there is gain to the intended receiver, and synthetic noise along directions in which there is not, can be arbitrarily far from capacity in this regime. Necessary and sufficient conditions for the secrecy capacity to be zero are provided, which simplify in the limit of many antennas when the entries of the channel matrices are independent and identically distributed. The resulting scaling laws establish that to prevent secure communication, the eavesdropper needs 3 times as many antennas as the sender and intended receiver have jointly, and that the optimimum division of antennas between sender and intended receiver is in the ratio of 2:1.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Secret-Key Generation using Correlated Sources and Channels

We study the problem of generating a shared secret key between two terminals in a joint source-channel setup -- the sender communicates to the receiver over a discrete memoryless wiretap channel and additionally the terminals have access to correlated discrete memoryless source sequences. We establish lower and upper bounds on the secret-key capacity. These bounds coincide, establishing the capacity, when the underlying channel consists of independent, parallel and reversely degraded wiretap channels. In the lower bound, the equivocation terms of the source and channel components are functionally additive. The secret-key rate is maximized by optimally balancing the the source and channel contributions. This tradeoff is illustrated in detail for the Gaussian case where it is also shown that Gaussian codebooks achieve the capacity. When the eavesdropper also observes a source sequence, the secret-key capacity is established when the sources and channels of the eavesdropper are a degraded version of the legitimate receiver. Finally the case when the terminals also have access to a public discussion channel is studied. We propose generating separate keys from the source and channel components and establish the optimality of this approach when the when the channel outputs of the receiver and the eavesdropper are conditionally independent given the input.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

A Simple Cooperative Diversity Method Based on Network Path Selection

Cooperative diversity has been recently proposed as a way to form virtual antenna arrays that provide dramatic gains in slow fading wireless environments. However most of the proposed solutions require distributed space-time coding algorithms, the careful design of which is left for future investigation if there is more than one cooperative relay. We propose a novel scheme, that alleviates these problems and provides diversity gains on the order of the number of relays in the network. Our scheme first selects the best relay from a set of M available relays and then uses this best relay for cooperation between the source and the destination. We develop and analyze a distributed method to select the best relay that requires no topology information and is based on local measurements of the instantaneous channel conditions. This method also requires no explicit communication among the relays. The success (or failure) to select the best available path depends on the statistics of the wireless channel, and a methodology to evaluate performance for any kind of wireless channel statistics, is provided. Information theoretic analysis of outage probability shows that our scheme achieves the same diversity-multiplexing tradeoff as achieved by more complex protocols, where coordination and distributed space-time coding for M nodes is required, such as those proposed in [7]. The simplicity of the technique, allows for immediate implementation in existing radio hardware and its adoption could provide for improved flexibility, reliability and efficiency in future 4G wireless systems.

0 citations0 reviewsNo code linkedOpen access