Neural networks increasingly run on hardware outside the user's control (cloud GPUs, inference marketplaces, edge specialized accelerators) for both training and inference. Yet ML-as-a-Service reveals little about what actually ran or whether returned outputs faithfully reflect the intended inputs and models. Users lack recourse against service downgrades such as model swaps, quantization, graph rewrites, or discrepancies like altered advertisement embeddings. Verifying outputs is especially difficult because floating-point execution on heterogeneous accelerators is inherently non-deterministic. Existing approaches like zkML, deterministic replay, TEEs, and replication are either impractical for real floating-point neural networks or reintroduce the need to trust the vendor. We present TAO: a Tolerance-Aware Optimistic verification protocol for floating-point neural networks that accepts outputs within principled operator-level acceptance regions rather than requiring bitwise equality. TAO combines two complementary error models: (i) sound per-operator IEEE-754 worst-case bounds and (ii) tight empirical percentile profiles calibrated across hardware types. Discrepancies are resolved via a Merkle-anchored, threshold-guided interactive dispute game that recursively partitions the traced computation graph until one operator remains; at the leaf, adjudication reduces to either a lightweight theoretical-bound check or a small honest-majority vote against empirical thresholds. Unchallenged results finalize after a challenge window, without requiring trusted hardware or deterministic kernels.

Model fingerprinting has emerged as a powerful tool for model owners to identify their shared model given API access. In order to lower false discovery rate, fight fingerprint leakage, and defend against coalitions of model users attempting to bypass detection, we argue that scaling up the number of fingerprints one can embed into a model, i.e. *Scalability* of fingerprints, is critical. Hence, we pose scalability as a crucial requirement for fingerprinting schemes. We experiment with fingerprint design at a scale significantly larger than previously considered, and introduce a new method, dubbed Perinucleus sampling, to generate scalable, persistent, and harmless fingerprints. We demonstrate that this scheme can add 24,576 fingerprints to a Llama-3.1-8B model---two orders of magnitude more than existing schemes---without degrading the model's utility. Our inserted fingerprints persist even after supervised fine-tuning on standard post-training data. We further address security risks for fingerprinting, and theoretically and empirically show how a scalable fingerprinting scheme like ours can mitigate these risks.

Recent reports claim that large language models (LLMs) now outperform elite humans in competitive programming. Drawing on knowledge from a group of medalists in international algorithmic contests, we revisit this claim, examining how LLMs differ from human experts and where limitations still remain. We introduce LiveCodeBench Pro, a benchmark composed of problems from Codeforces, ICPC, and IOI that are continuously updated to reduce the likelihood of data contamination. A team of Olympiad medalists annotates every problem for algorithmic categories and conducts a line-by-line analysis of failed model-generated submissions. Using this new data and benchmark, we find that frontier models still have significant limitations: without external tools, the best model achieves only 53\% pass@1 on medium-difficulty problems and 0\% on hard problems, domains where expert humans still excel. We also find that LLMs succeed at implementation-heavy problems but struggle with nuanced algorithmic reasoning and complex case analysis, often generating confidently incorrect justifications. High performance appears largely driven by implementation precision and tool augmentation, not superior reasoning. LiveCodeBench Pro thus highlights the significant gap to human grandmaster levels, while offering fine-grained diagnostics to steer future improvements in code-centric LLM reasoning.

Decentralized finance (DeFi) borrowing and lending platforms are crucial to the decentralized economy, involving two main participants: lenders who provide assets for interest and borrowers who offer collateral exceeding their debt and pay interest. Collateral volatility necessitates over-collateralization to protect lenders and ensure competitive returns. Traditional DeFi platforms use a fixed interest rate curve based on the utilization rate (the fraction of available assets borrowed) and determine over-collateralization offline through simulations to manage risk. This method doesn't adapt well to dynamic market changes, such as price fluctuations and evolving user needs, often resulting in losses for lenders or borrowers. In this paper, we introduce an adaptive, data-driven protocol for DeFi borrowing and lending. Our approach includes a high-frequency controller that dynamically adjusts interest rates to maintain market stability and competitiveness with external markets. Unlike traditional protocols, which rely on user reactions and often adjust slowly, our controller uses a learning-based algorithm to quickly find optimal interest rates, reducing the opportunity cost for users during periods of misalignment with external rates. Additionally, we use a low-frequency planner that analyzes user behavior to set an optimal over-collateralization ratio, balancing risk reduction with profit maximization over the long term. This dual approach is essential for adaptive markets: the short-term component maintains market stability, preventing exploitation, while the long-term planner optimizes market parameters to enhance profitability and reduce risks. We provide theoretical guarantees on the convergence rates and adversarial robustness of the short-term component and the long-term effectiveness of our protocol. Empirical validation confirms our protocol's theoretical benefits.

Automated Market Makers (AMMs) are essential in Decentralized Finance (DeFi) as they match liquidity supply with demand. They function through liquidity providers (LPs) who deposit assets into liquidity pools. However, the asset trading prices in these pools often trail behind those in more dynamic, centralized exchanges, leading to potential arbitrage losses for LPs. This issue is tackled by adapting market maker bonding curves to trader behavior, based on the classical market microstructure model of Glosten and Milgrom. Our approach ensures a zero-profit condition for the market maker's prices. We derive the differential equation that an optimal adaptive curve should follow to minimize arbitrage losses while remaining competitive. Solutions to this optimality equation are obtained for standard Gaussian and Lognormal price models using Kalman filtering. A key feature of our method is its ability to estimate the external market price without relying on price or loss oracles. We also provide an equivalent differential equation for the implied dynamics of canonical static bonding curves and establish conditions for their optimality. Our algorithms demonstrate robustness to changing market conditions and adversarial perturbations, and we offer an on-chain implementation using Uniswap v4 alongside off-chain AI co-processors.

Layer 1 (L1) blockchains such as Ethereum are secured under an "honest supermajority of stake" assumption for a large pool of validators who verify each and every transaction on it. This high security comes at a scalability cost which not only effects the throughput of the blockchain but also results in high gas fees for executing transactions on chain. The most successful solution for this problem is provided by optimistic rollups, Layer 2 (L2) blockchains that execute transactions outside L1 but post the transaction data on L1. The security for such L2 chains is argued, informally, under the assumption that a set of nodes will check the transaction data posted on L1 and raise an alarm (a fraud proof) if faulty transactions are detected. However, all current deployments lack a proper incentive mechanism for ensuring that these nodes will do their job "diligently", and simply rely on a cursory incentive alignment argument for security. We solve this problem by introducing an incentivized watchtower network designed to serve as the first line of defense for rollups. Our main contribution is a "Proof of Diligence" protocol that requires watchtowers to continuously provide a proof that they have verified L2 assertions and get rewarded for the same. Proof of Diligence protocol includes a carefully-designed incentive mechanism that is provably secure when watchtowers are rational actors, under a mild rational independence assumption. Our proposed system is now live on Ethereum testnet. We deployed a watchtower network and implemented Proof of Diligence for multiple optimistic rollups. We extract execution as well as inclusion proofs for transactions as a part of the bounty. Each watchtower has minimal additional computational overhead beyond access to standard L1 and L2 RPC nodes. Our watchtower network comprises of 10 different (rationally independent) EigenLayer operators, secured using restaked Ethereum and spread across three different continents, watching two different optimistic rollups for Ethereum, providing them a decentralized and trustfree first line of defense. The watchtower network can be configured to watch the batches committed by sequencer on L1, providing an approximately 3 minute (cryptoeconomically secure) finality since the additional overhead for watching is very low. This is much lower than the finality delay in the current setup where it takes about 45 minutes for state assertions on L1, and hence will not delay the finality process on L1.

Crash fault tolerant (CFT) consensus algorithms are commonly used in scenarios where system components are trusted -- e.g., enterprise settings and government infrastructure. However, CFT consensus can be broken by even a single corrupt node. A desirable property in the face of such potential Byzantine faults is \emph{accountability}: if a corrupt node breaks protocol and affects consensus safety, it should be possible to identify the culpable components with cryptographic integrity from the node states. Today, the best-known protocol for providing accountability to CFT protocols is called PeerReview; it essentially records a signed transcript of all messages sent during the CFT protocol. Because PeerReview is agnostic to the underlying CFT protocol, it incurs high communication and storage overhead. We propose CFT-Forensics, an accountability framework for CFT protocols. We show that for a special family of \emph{forensics-compliant} CFT protocols (which includes widely-used CFT protocols like Raft and multi-Paxos), CFT-Forensics gives provable accountability guarantees. Under realistic deployment settings, we show theoretically that CFT-Forensics operates at a fraction of the cost of PeerReview. We subsequently instantiate CFT-Forensics for Raft, and implement Raft-Forensics as an extension to the popular nuRaft library. In extensive experiments, we demonstrate that Raft-Forensics adds low overhead to vanilla Raft. With 256 byte messages, Raft-Forensics achieves a peak throughput 87.8\% of vanilla Raft at 46\% higher latency ($+44$ ms). We finally integrate Raft-Forensics into the open-source central bank digital currency OpenCBDC, and show that in wide-area network experiments, Raft-Forensics achieves 97.8\% of the throughput of Raft, with 14.5\% higher latency ($+326$ ms).

Progress in designing channel codes has been driven by human ingenuity and, fittingly, has been sporadic. Polar codes, developed on the foundation of Arikan’s polarization kernel, represent the latest breakthrough in coding theory and have emerged as the state-of-the-art error-correction code for short-to-medium block length regimes. In an effort to automate the invention of good channel codes, especially in this regime, we explore a novel, non-linear generalization of Polar codes, which we call DeepPolar codes. DeepPolar codes extend the conventional Polar coding framework by utilizing a larger kernel size and parameterizing these kernels and matched decoders through neural networks. Our results demonstrate that these data-driven codes effectively leverage the benefits of a larger kernel size, resulting in enhanced reliability when compared to both existing neural codes and conventional Polar codes.

Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. In this paper, we propose a family of protocols in which multiple blockchains interact to create a combined ledger with boosted trust. We show that even if several of the interacting blockchains cease to provide security guarantees, the combined ledger continues to be secure - our Trustboost protocols achieve the optimal threshold of tolerating the insecure blockchains. This optimality, along with the necessity of blockchain interactions, is formally shown within the classic shared memory model, tackling the long standing open challenge of solving consensus in the presence of both Byzantine objects and processes. Furthermore, our proposed construction of Trustboost simply operates via smart contracts and require no change to the underlying consensus protocols of the participating blockchains, a form of "consensus on top of consensus''. The protocols are lightweight and can be used on specific (e.g., high value) transactions; we demonstrate the practicality by implementing and deploying Trustboost as cross-chain smart contracts in the Cosmos ecosystem using approximately 3,000 lines of Rust code, made available as open source [52]. Our evaluation shows that using 10 Cosmos chains in a local testnet, Trustboost has a gas cost of roughly $2 with a latency of 2 minutes per request, which is in line with the cost on a high security chain such as Bitcoin or Ethereum.

Polar codes are widely used state-of-the-art codes for reliable communication that have recently been included in the $5^{\text{th}}$ generation wireless standards ($5$G). However, there still remains room for design of polar decoders that are both efficient and reliable in the short blocklength regime. Motivated by recent successes of data-driven channel decoders, we introduce a novel $\textbf{ C}$ur${\textbf{RI}}$culum based $\textbf{S}$equential neural decoder for $\textbf{P}$olar codes (CRISP). We design a principled curriculum, guided by information-theoretic insights, to train CRISP and show that it outperforms the successive-cancellation (SC) decoder and attains near-optimal reliability performance on the $\text{Polar}(32,16)$ and $\text{Polar}(64,22)$ codes. The choice of the proposed curriculum is critical in achieving the accuracy gains of CRISP, as we show by comparing against other curricula. More notably, CRISP can be readily extended to Polarization-Adjusted-Convolutional (PAC) codes, where existing SC decoders are significantly less reliable. To the best of our knowledge, CRISP constructs the first data-driven decoder for PAC codes and attains near-optimal performance on the $\text{PAC}(32,16)$ code.

In modern communication systems with feedback, there are increasingly more scenarios where the transmitter has much less power than the receiver (e.g., medical implant devices), which we refer to as noise-asymmetric channels. For such channels, the feedback link is of higher quality than the forward link. However, feedback schemes for cellular communications, such as hybrid ARQ, do not fully utilize the high-quality feedback link. To this end, we introduce Compressed Error Hybrid ARQ, a generalization of hybrid ARQ tailored for noise-asymmetric channels; the receiver sends its estimated message to the transmitter, and the transmitter harmoniously switches between hybrid ARQ and compressed error retransmission. We show that our proposed method significantly improves reliability, latency, and spectral efficiency compared to the conventional hybrid ARQ in various practical scenarios where the transmitter is resource-constrained.

Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded.

Decentralized cellular networks have emerged to increase network accessibility by distributing infrastructure ownership over independent entities. Unlike the centralized setting, these architectures can allow users to connect to any untrusted base station without prior subscription. However, verification of the service is necessary in the absence of trust for commensurate payments by the user. Further, any method of verification must be non-intrusive and reliably agreed upon by the involved parties. To this end, we describe two-sided measurements where both the users and the providers independently assess the cellular service. We find that reconciling measurements from different layers of the cellular stack for a diverse set of matching observations is challenging but not impossible. Hence, new use cases such as a decentralized slicing marketplace, and contract-free roaming can be enabled by two-sided measurements. We envision applying two-sided measurements to real-time, on-demand network slicing and present an architecture that is capable of offering, as well as verifying, such slices in a scalable manner.

In this paper, we introduce a neural-augmented decoder for Turbo codes called TINYTURBO . TINYTURBO has complexity comparable to the classical max-log-MAP algorithm but has much better reliability than the max-log-MAP baseline and performs close to the MAP algorithm. We show that TINYTURBO exhibits strong robustness on a variety of practical channels of interest, such as EPA and EVA channels, which are included in the LTE standards. We also show that TINYTURBO strongly generalizes across different rate, blocklengths, and trellises. We verify the reliability and efficiency of TINYTURBO via over-the-air experiments.

Proof of Work (PoW) blockchains are susceptible to adversarial majority mining attacks in the early stages due to incipient participation and corresponding low net hash power. Bootstrapping ensures safety and liveness during the transient stage by protecting against a majority mining attack, allowing a PoW chain to grow the participation base and corresponding mining hash power. Liveness is especially important since a loss of liveness will lead to loss of honest mining rewards, decreasing honest participation, hence creating an undesired spiral; indeed existing bootstrapping mechanisms offer especially weak liveness guarantees.

Byzantine fault-tolerant (BFT) protocols allow a group of replicas to come to consensus even when some of the replicas are Byzantine faulty. There exist multiple BFT protocols to securely tolerate an optimal number of faults t under different network settings. However, if the number of faults f exceeds t then security could be violated. In this paper we mathematically formalize the study of forensic support of BFT protocols: we aim to identify (with cryptographic integrity) as many of the malicious replicas as possible and in as distributed manner as possible. Our main result is that forensic support of BFT protocols depends heavily on minor implementation details that do not affect the protocol's security or complexity. Focusing on popular BFT protocols (PBFT, HotStuff, Algorand) we exactly characterize their forensic support, showing that there exist minor variants of each protocol for which the forensic supports vary widely. We show strong forensic support capability of LibraBFT, the consensus protocol of Diem cryptocurrency; our lightweight forensic module implemented on a Diem client is open-sourced and is under active consideration for deployment in Diem. Finally, we show that all secure BFT protocols designed for 2t+1 replicas communicating over a synchronous network forensic support is inherently nonexistent; this impossibility result holds for all BFT protocols and even if one has access to the states of all replicas (including Byzantine ones).

Several emerging proof-of-work (PoW) blockchain protocols rely on a ''parallel-chain'' architecture for scaling, where instead of a single chain, multiple chains are run in parallel and aggregated. A key requirement of practical PoW blockchains is to adapt to mining power variations over time (Bitcoin's total mining power has increased by a 1014 factor over the decade). In this paper, we consider the design of provably secure parallel-chain protocols which can adapt to such mining power variations.

Landmark codes underpin reliable physical layer communication, e.g., Reed-Muller, BCH, Convolution, Turbo, LDPC, and Polar codes: each is a linear code and represents a mathematical breakthrough. The impact on humanity is huge: each of these codes has been used in global wireless communication standards (satellite, WiFi, cellular). Reliability of communication over the classical additive white Gaussian noise (AWGN) channel enables benchmarking and ranking of the different codes. In this paper, we construct KO codes, a computationally efficient family of deep-learning driven (encoder, decoder) pairs that outperform the state-of-the-art reliability performance on the standardized AWGN channel. KO codes beat state-of-the-art Reed-Muller and Polar codes, under the low-complexity successive cancellation decoding, in the challenging short-to-medium block length regime on the AWGN channel. We show that the gains of KO codes are primarily due to the nonlinear mapping of information bits directly to transmit symbols (bypassing modulation) and yet possess an efficient, high-performance decoder. The key technical innovation that renders this possible is design of a novel family of neural architectures inspired by the computation tree of the {\bf K}ronecker {\bf O}peration (KO) central to Reed-Muller and Polar codes. These architectures pave way for the discovery of a much richer class of hitherto unexplored nonlinear algebraic structures.

Reed-Muller (RM) codes are conjectured to achieve the capacity of any binary-input memoryless symmetric (BMS) channel, and are observed to have a comparable performance to that of random codes in terms of scaling laws. On the negative side, RM codes lack efficient decoders with performance close to that of a maximum likelihood decoder for general parameters. Also, they only admit certain discrete sets of rates. In this paper, we focus on subcodes of RM codes with flexible rates that can take any code dimension from 1 to$n$. where$n$is the blocklength. We first extend the recursive projection-aggregation (RPA) algorithm proposed recently by Ye and Abbe for decoding RM codes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different ways for pruning the projections. We then derive the soft-decision based version of our algorithm, called soft-subRPA, that is shown to improve upon the performance of subRPA. Furthermore, it enables training a machine learning (ML) model to search for good sets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly reduced number of projections. For instance, our simulation results on a (64,14) RM subcode show almost identical performance for full-projection decoding and pruned-projection decoding with 15 projections picked via training our ML model. This is equivalent to lowering the complexity by a factor of more than 4 without sacrificing the decoding performance.

Gating is a key feature in modern neural networks including LSTMs, GRUs and sparsely-gated deep neural networks. The backbone of such gated networks is a mixture-of-experts layer, where several experts make regression decisions and gating controls how to weigh the decisions in an input-dependent manner. Despite having such a prominent role in both modern and classical machine learning, very little is understood about parameter recovery of mixture-of-experts since gradient descent and EM algorithms are known to be stuck in local optima in such models.In this paper, we perform a careful analysis of the optimization landscape and show that with appropriately designed loss functions, gradient descent can indeed learn the parameters accurately. A key idea underpinning our results is the design of two {\em distinct} loss functions, one for recovering the expert parameters and another for recovering the gating parameters. We demonstrate the first sample complexity results for parameter recovery in this model for any algorithm and demonstrate significant performance gains over standard loss functions in numerical experiments.

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

The meaning of a word is closely linked to sociocultural factors that can change over time and location, resulting in corresponding meaning changes.Taking a global view of words and their meanings in a widely used language, such as English, may require us to capture more refined semantics for use in time-specific or location-aware situations, such as the study of cultural trends or language use.However, popular vector representations for words do not adequately include temporal or spatial information.In this work, we present a model for learning word representation conditioned on time and location.In addition to capturing meaning changes over time and location, we require that the resulting word embeddings retain salient semantic and geometric properties.We train our model on time-and locationstamped corpora, and show using both quantitative and qualitative evaluations that it can capture semantics across time and locations.We note that our model compares favorably with the state-of-the-art for time-specific embedding, and serves as a new benchmark for location-specific embeddings.

Designing channel codes is one of the core research areas for modern communication systems. Canonical channel codes asymptotically achieve near-capacity performance under large block length regime for additive white gaussian noise channels. However, this achieved success does not generalize to many channels. Channels with output feedback, proposed by Shannon, is one of such channels where practical codes have been unknown for several decades.Recently it has been demonstrated that deep learning based code outperforms the state-of-the-art codes for channels with output feedback. While the success is promising and inspiring, there are a few major challenges that need to be addressed. Firstly, the channel assumes a feedback with a unit step delay, which is not very practical. Second is the lack of generalization to larger block lengths. In this work, we propose Feedback Auto Turbo Encoder (FTAE) which harmoniously combines interleaver and iterative decoding with CNN architectures and demonstrate the blocklength gain and improved performance in the block feedback setting.

Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

Significant advances have been made recently on training neural networks, where the main challenge is in solving an optimization problem with abundant critical points. However, existing approaches to address this issue crucially rely on a restrictive assumption: the training data is drawn from a Gaussian distribution. In this paper, we provide a novel unified framework to design loss functions with desirable landscape properties for a wide range of general input distributions. On these loss functions, remarkably, stochastic gradient descent theoretically recovers the true parameters with \emph{global} initializations and empirically outperforms the existing approaches. Our loss function design bridges the notion of score functions with the topic of neural network optimization. Central to our approach is the task of estimating the score function from samples, which is of basic and independent interest to theoretical statistics. Traditional estimation methods (example: kernel based) fail right at the outset; we bring statistical methods of local likelihood to design a novel estimator of score functions, that provably adapts to the local geometry of the unknown density.

The concept of a blockchain was invented by Satoshi Nakamoto to maintain a distributed ledger. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput and confirmation latency. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay product CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing Nakamoto's blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.

Designing channel codes under low latency constraints is one of the most demanding requirements in 5G standards. However, sharp characterizations of the performances of traditional codes are only available in the large block lengths limit. Code designs are guided by those asymptotic analyses and require large block lengths and long latency to achieve the desired error rate. Furthermore, when the codes designed for one channel (e.g. Additive White Gaussian Noise (AWGN) channel) are used for another (e.g. non-AWGN channels), heuristics are necessary to achieve any non trivial performance - thereby severely lacking in robustness as well as adaptivity. Obtained by jointly designing recurrent neural network (RNN) based encoder and decoder, we propose an end-to-end learned neural code which outperforms canonical convolutional code under block settings. With this gained experience of designing a novel neural block code, we propose a new class of codes under low latency constraint - Low-latency Efficient Adaptive Robust Neural (LEARN) codes, which outperform the state-of-the-art low latency codes as well as exhibit robustness and adaptivity properties. LEARN codes show the potential of designing new versatile and universal codes for future communications via tools of modern deep learning coupled with communication engineering insights.

Mixture-of-Experts (MoE) is a widely popular model for ensemble learning and is a basic building block of highly successful modern neural networks as well as a component in Gated Recurrent Units (GRU) and Attention networks. However, present algorithms for learning MoE, including the EM algorithm and gradient descent, are known to get stuck in local optima. From a theoretical viewpoint, finding an efficient and provably consistent algorithm to learn the parameters remains a long standing open problem for more than two decades. In this paper, we introduce the first algorithm that learns the true parameters of a MoE model for a wide class of non-linearities with global consistency guarantees. While existing algorithms jointly or iteratively estimate the expert parameters and the gating parameters in the MoE, we propose a novel algorithm that breaks the deadlock and can directly estimate the expert parameters by sensing its echo in a carefully designed cross-moment tensor between the inputs and the output. Once the experts are known, the recovery of gating parameters still requires an EM algorithm; however, we show that the EM algorithm for this simplified problem, unlike the joint EM algorithm, converges to the true parameters. We empirically validate our algorithm on both the synthetic and real data sets in a variety of settings, and show superior performance to standard baselines.

A blockchain is a database of sequential events that is maintained by a distributed group of nodes. A key consensus problem in blockchains is that of determining the next block (data element) in the sequence. Many blockchains address this by electing a new node to propose each new block. The new block is (typically) appended to the tip of the proposer's local blockchain, and subsequently broadcast to the rest of the network. Without network delay (or adversarial behavior), this procedure would give a perfect chain, since each proposer would have the same view of the blockchain. A major challenge in practice is forking. Due to network delays, a proposer may not yet have the most recent block, and may therefore create a side chain that branches from the middle of the main chain. Forking reduces throughput, since only one a single main chain can survive, and all other blocks are discarded. We propose a new P2P protocol for blockchains called Barracuda, in which each proposer, prior to proposing a block, polls ℓ other nodes for their local blocktree information. Under a stochastic network model, we prove that this lightweight primitive improves throughput as if the entire network were a factor of ℓ faster. We provide guidelines on how to implement Barracuda in practice, guaranteeing robustness against several real-world factors.

Designing codes that combat the noise in a communication medium has remained a significant area of research in information theory as well as wireless communications. Asymptotically optimal channel codes have been developed by mathematicians for communicating under canonical models after over 60 years of research. On the other hand, in many non-canonical channel settings, optimal codes do not exist and the codes designed for canonical models are adapted via heuristics to these channels and are thus not guaranteed to be optimal. In this work, we make significant progress on this problem by designing a fully end-to-end jointly trained neural encoder and decoder, namely, Turbo Autoencoder (TurboAE), with the following contributions: (a) under moderate block lengths, TurboAE approaches state-of-the-art performance under canonical channels; (b) moreover, TurboAE outperforms the state-of-the-art codes under non-canonical settings in terms of reliability. TurboAE shows that the development of channel coding design can be automated via deep learning, with near-optimal performance.

We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.

Misspelled words of the malicious kind work by changing specific keywords and are intended to thwart existing automated applications for cyber-environment control such as harassing content detection on the Internet and email spam detection. In this paper, we focus on malicious spelling correction, which requires an approach that relies on the context and the surface forms of targeted keywords. In the context of two applications-profanity detection and email spam detection-we show that malicious misspellings seriously degrade their performance. We then propose a context-sensitive approach for malicious spelling correction using word embeddings and demonstrate its superior performance compared to state-of-the-art spell checkers.

Prepositions are highly polysemous, and their variegated senses encode significant semantic information.In this paper we match each preposition's left-and right context, and their interplay to the geometry of the word vectors to the left and right of the preposition.Extracting these features from a large corpus and using them with machine learning models makes for an efficient preposition sense disambiguation (PSD) algorithm, which is comparable to and better than state-of-the-art on two benchmark datasets.Our reliance on no linguistic tool allows us to scale the PSD algorithm to a large corpus and learn sensespecific preposition representations.The crucial abstraction of preposition senses as word representations permits their use in downstream applications-phrasal verb paraphrasing and preposition selection-with new state-ofthe-art results.

With the growing usage of Bitcoin and other cryptocurrencies, many scalability challenges have emerged. A promising scaling solution, exemplified by the Lightning Network, uses a network of bidirectional payment channels that allows fast transactions between two parties. However, routing payments on these networks efficiently is non-trivial, since payments require finding paths with sufficient funds, and channels can become unidirectional over time blocking further transactions through them. Today's payment channel networks exacerbate these problems by attempting to deliver all payments atomically.

Hongyu Gong, Suma Bhat, Pramod Viswanath. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

The design of codes for communicating reliably over a statistically well defined channel is an important endeavor involving deep mathematical research and wide- ranging practical applications. In this work, we present the first family of codes obtained via deep learning, which significantly beats state-of-the-art codes designed over several decades of research. The communication channel under consideration is the Gaussian noise channel with feedback, whose study was initiated by Shannon; feedback is known theoretically to improve reliability of communication, but no practical codes that do so have ever been successfully constructed. We break this logjam by integrating information theoretic insights harmoniously with recurrent-neural-network based encoders and decoders to create novel codes that outperform known codes by 3 orders of magnitude in reliability. We also demonstrate several desirable properties in the codes: (a) generalization to larger block lengths; (b) composability with known codes; (c) adaptation to practical constraints. This result also presents broader ramifications to coding theory: even when the channel has a clear mathematical model, deep learning methodologies, when combined with channel specific information-theoretic insights, can potentially beat state-of-the-art codes, constructed over decades of mathematical research.

Information theoretic quantities play an important role in various settings in machine learning, including causality testing, structure inference in graphical models, time-series problems, feature selection as well as in providing privacy guarantees. A key quantity of interest is the mutual information and generalizations thereof, including conditional mutual information, multivariate mutual information, total correlation and directed information. While the aforementioned information quantities are well defined in arbitrary probability spaces, existing estimators employ a $\Sigma H$ method, which can only work in purely discrete space or purely continuous case since entropy (or differential entropy) is well defined only in that regime. In this paper, we define a general graph divergence measure ($\mathbb{GDM}$), generalizing the aforementioned information measures and we construct a novel estimator via a coupling trick that directly estimates these multivariate information measures using the Radon-Nikodym derivative. These estimators are proven to be consistent in a general setting which includes several cases where the existing estimators fail, thus providing the only known estimators for the following settings: (1) the data has some discrete and some continuous valued components (2) some (or all) of the components themselves are discrete-continuous \textit{mixtures} (3) the data is real-valued but does not have a joint density on the entire space, rather is supported on a low-dimensional manifold. We show that our proposed estimators significantly outperform known estimators on synthetic and real datasets.

Estimators of information theoretic measures, such as entropy and mutual information, are a basic workhorse for many downstream applications in modern data science. State-of-the-art approaches have been either geometric [nearest neighbor (NN)-based] or kernel-based (with a globally chosen bandwidth). In this paper, we combine both these approaches to design new estimators of entropy and mutual information that outperform the state-of-the-art methods. Our estimator uses local bandwidth choices of k -NN distances with a finite k , independent of the sample size. Such a local and data dependent choice ameliorates boundary bias and improves performance in practice, but the bandwidth is vanishing at a fast rate, leading to a non-vanishing bias. We show that the asymptotic bias of the proposed estimator is universal; it is independent of the underlying distribution. Hence, it can be precomputed and subtracted from the estimate. As a byproduct, we obtain a unified way of obtaining both the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.

Estimating mutual information from independent identically distributed samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is the one proposed by Kraskov, Stögbauer, and Grassberger (KSG) in 2004 and is nonparametric and based on the distances of each sample to its kthnearest neighboring sample, where k is a fixed small integer. Despite of its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper, we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the ℓ2error as a function of a number of samples. We argue that the performance benefits of the KSG estimator stems from a curious “correlation boosting” effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a by-product of our investigations, we obtain nearly tight rates of convergence of the ℓ2error of the well-known fixed k-nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

This paper proposes a simple test for compositionality (i.e., literal usage) of a word or phrase in a context-specific way. The test is computationally simple, relying on no external resources and only uses a set of trained word vectors. Experiments show that the proposed method is competitive with state of the art and displays high accuracy in context-specific compositionality detection of a variety of natural language phenomena (idiomaticity, sarcasm, metaphor) for different datasets in multiple languages. The key insight is to connect compositionality to a curious geometric property of word embeddings, which is of independent interest.

In this paper we present a novel framework for morpheme segmentation which uses the morpho-syntactic regularities preserved by word representations, in addition to orthographic features, to segment words into morphemes.This framework is the first to consider vocabulary-wide syntactico-semantic information for this task.We also analyze the deficiencies of available benchmarking datasets and introduce our own dataset that was created on the basis of compositionality.We validate our algorithm across different datasets and languages and present new state-of-the-art results.

Estimating mutual information from i.i.d. samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is one proposed by Kraskov and Stogbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its kthnearest neighboring sample, where k is a fixed small integer. Despite its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the ℓ2error as a function of number of samples. We argue that the performance benefits of the KSG estimator stems from a curious “correlation boosting” effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a byproduct of our investigations, we obtain nearly tight rates of convergence of the ℓ2error of the well known fixed k nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

Estimating expected polynomials of density functions from samples is a basic problem with numerous applications in statistics and information theory. Although kernel density estimators are widely used in practice for such functional estimation problems, practitioners are left on their own to choose an appropriate bandwidth for each application in hand. Further, kernel density estimators suffer from boundary biases, which are prevalent in real world data with lower dimensional structures. We propose using the fixed-k nearest neighbor distances for the bandwidth, which adaptively adjusts to local geometry. Further, we propose a novel estimator based on local likelihood density estimators, that mitigates the boundary biases. Although such a choice of fixed-k nearest neighbor distances to bandwidths results in inconsistent estimators, we provide a simple debiasing scheme that precomputes the asymptotic bias and divides off this term. With this novel correction, we show consistency of this debiased estimator. We provide numerical experiments suggesting that it improves upon competing state-of-the-art methods.

Recent attacks on Bitcoin's peer-to-peer (P2P) network demonstrated that its transaction-flooding protocols, which are used to ensure network consistency, may enable user deanonymization---the linkage of a user's IP address with her pseudonym in the Bitcoin network. In 2015, the Bitcoin community responded to these attacks by changing the network's flooding mechanism to a different protocol, known as diffusion. However, it is unclear if diffusion actually improves the system's anonymity. In this paper, we model the Bitcoin networking stack and analyze its anonymity properties, both pre- and post-2015. The core problem is one of epidemic source inference over graphs, where the observational model and spreading mechanisms are informed by Bitcoin's implementation; notably, these models have not been studied in the epidemic source detection literature before. We identify and analyze near-optimal source estimators. This analysis suggests that Bitcoin's networking protocols (both pre- and post-2015) offer poor anonymity properties on networks with a regular-tree topology. We confirm this claim in simulation on a 2015 snapshot of the real Bitcoin P2P network topology.

Estimation of mutual information from observed samples is a basic primitive in machine learning, useful in several learning tasks including correlation mining, information bottleneck, Chow-Liu tree, and conditional independence testing in (causal) graphical models. While mutual information is a quantity well-defined for general probability spaces, estimators have been developed only in the special case of discrete or continuous pairs of random variables. Most of these estimators operate using the 3H -principle, i.e., by calculating the three (differential) entropies of X, Y and the pair (X,Y). However, in general mixture spaces, such individual entropies are not well defined, even though mutual information is. In this paper, we develop a novel estimator for estimating mutual information in discrete-continuous mixtures. We prove the consistency of this estimator theoretically as well as demonstrate its excellent empirical performance. This problem is relevant in a wide-array of applications, where some variables are discrete, some continuous, and others are a mixture between continuous and discrete components.

Discovering a correlation from one variable to another variable is of fundamental scientific and practical interest. While existing correlation measures are suitable for discovering average correlation, they fail to discover hidden or potential correlations. To bridge this gap, (i) we postulate a set of natural axioms that we expect a measure of potential correlation to satisfy; (ii) we show that the rate of information bottleneck, i.e., the hypercontractivity coefficient, satisfies all the proposed axioms; (iii) we provide a novel estimator to estimate the hypercontractivity coefficient from samples; and (iv) we provide numerical experiments demonstrating that this proposed estimator discovers potential correlations among various indicators of WHO datasets, is robust in discovering gene interactions from gene expression time series data, and is statistically more powerful than the estimators for other correlation measures in binary hypothesis testing of canonical examples of potential correlations.

Anonymous social media platforms, like Secret, Yik Yak, and Whisper, have emerged as important tools for sharing ideas without the fear of judgment. Such anonymous platforms are also important in nations under authoritarian rule, where freedom of expression and the personal safety of message that authors may depend on anonymity. Whether for fear of judgment or retribution, it is sometimes crucial to hide the identities of users who post sensitive messages. In this paper, we consider a global adversary who wishes to identify the author of a message; it observes either a snapshot of the spread of a message at a certain time or sampled timestamp metadata, or both. Recent advances in rumor source detection show that existing messaging protocols are vulnerable against such an adversary. We introduce a novel messaging protocol, which we call adaptive diffusion, and show that under the snapshot adversarial model, adaptive diffusion spreads content fast and achieves perfect obfuscation of the source when the underlying contact network is an infinite regular tree. That is, all users with the message are nearly equally likely to have been the origin of the message. When the contact network is an irregular tree, we characterize the probability of maximum likelihood detection by proving a concentration result over Galton-Watson trees. Experiments on a sampled Facebook network demonstrate that adaptive diffusion effectively hides the location of the source even when the graph is finite, is irregular, and has cycles.

Sequential querying of differentially private mechanisms degrades the overall privacy level. In this paper, we answer the fundamental question of characterizing the level of overall privacy degradation as a function of the number of queries and the privacy levels maintained by each privatization mechanism. Our solution is complete: we prove an upper bound on the overall privacy level and construct a sequence of privatization mechanisms that achieves this bound. The key innovation is the introduction of an operational interpretation of differential privacy (involving hypothesis testing) and the use of a data processing inequality along with its converse. Our result improves over the state of the art, and has immediate connections to several problems studied in the literature.

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

Anonymous messaging platforms like Whisper and Yik Yak allow users to spread messages over a network (e.g., a social network) without revealing message authorship to other users. The spread of messages on these platforms can be modeled by a diffusion process over a graph. Recent advances in network analysis have revealed that such diffusion processes are vulnerable to author deanonymization by adversaries with access to metadata, such as timing information. In this work, we ask the fundamental question of how to propagate anonymous messages over a graph to make it difficult for adversaries to infer the source. In particular, we study the performance of a message propagation protocol called adaptive diffusion introduced in (Fanti et al., 2015). We prove that when the adversary has access to metadata at a fraction of corrupted graph nodes, adaptive diffusion achieves asymptotically optimal source-hiding and significantly outperforms standard diffusion. We further demonstrate empirically that adaptive diffusion hides the source effectively on real social networks.

We consider axiomatically the problem of estimating the strength of a conditional dependence relationship P_Y|X from a random variables X to a random variable Y. This has applications in determining the strength of a known causal relationship, where the strength depends only on the conditional distribution of the effect given the cause (and not on the driving distribution of the cause). Shannon capacity, appropriately regularized, emerges as a natural measure under these axioms. We examine the problem of calculating Shannon capacity from the observed samples and propose a novel fixed-k nearest neighbor estimator, and demonstrate its consistency. Finally, we demonstrate an application to single-cell flow-cytometry, where the proposed estimators significantly reduce sample complexity.

A simulation of an interactive protocol entails the use of interactive communication to produce the output of the protocol to within a fixed statistical distance ε. Recent works have proposed that the information complexity of the protocol plays a central role in characterizing the minimum number of bits that the parties must exchange for a successful simulation, namely the distributional communication complexity of simulating the protocol. Several simulation protocols have been proposed with communication complexity depending on the information complexity of the simulated protocol. However, in the absence of any general lower bounds for distributional communication complexity, the conjectured central role of information complexity is far from settled. We fill this gap and show that the distributional communication complexity of ε-simulating a protocol is bounded below by the ε-tail λε of the information complexity density, a random variable with information complexity as its expected value. For protocols with bounded number of rounds, we give a simulation protocol that yields a matching upper bound. Thus, it is not information complexity but λε that governs the distributional communication complexity.

Estimators of information theoretic measures such as entropy and mutual information from samples are a basic workhorse for many downstream applications in modern data science. State of the art approaches have been either geometric (nearest neighbor (NN) based) or kernel based (with bandwidth chosen to be data independent and vanishing sub linearly in the sample size). In this paper we combine both these approaches to design new estimators of entropy and mutual information that strongly outperform all state of the art methods. Our estimator uses bandwidth choice of fixed $k$-NN distances; such a choice is both data dependent and linearly vanishing in the sample size and necessitates a bias cancellation term that is universal and independent of the underlying distribution. As a byproduct, we obtain a unified way of obtaining both kernel and NN estimators. The corresponding theoretical contribution relating the geometry of NN distances to asymptotic order statistics is of independent mathematical interest.

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. Messages in these applications propagate anonymously (without authorship metadata) over a network that is typically defined by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by statistical inference attacks. Adaptive diffusion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, node degrees differ from node to node, and adaptive diffusion can be significantly sub-optimal. This gap increases as the degrees become more irregular.

Hybrid switching -- in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch -- is a promising alternative to interconnect servers in today's large scale data centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly-optimal scheduling algorithm that trades-off reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution towards a constructive version of Caratheodory's Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi-hop routing, distinct from the well-known load balancing effects.

Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where both the data providers and data analysts want to maximize the utility of statistical analyses performed on the released data, we study the fundamental trade-off between local differential privacy and utility. This trade-off is formulated as a constrained optimization problem: maximize utility subject to local differential privacy constraints. We introduce a combinatorial family of extremal privatization mechanisms, which we call staircase mechanisms, and show that it contains the optimal privatization mechanisms for a broad class of information theoretic utilities such as mutual information and $f$-divergences. We further prove that for any utility function and any privacy level, solving the privacy-utility maximization problem is equivalent to solving a finite-dimensional linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the size of the alphabet the data lives in. To account for this, we show that two simple privatization mechanisms, the binary and randomized response mechanisms, are universally optimal in the low and high privacy regimes, and well approximate the intermediate regime.

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queriesqueries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal ϵ-differentially private mechanism for a single realvalued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ℓ1and ℓ2cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (ϵ is small), the Laplacian mechanism is asymptotically optimal as ϵ → 0; in the low privacy regime (ϵ is large), the minimum magnitude and second moment of noise are Θ(Δe(-ϵ/2)) and Θ(Δ2e(-2ϵ/3)) as ϵ → +∞, respectively, while the corresponding figures when using the Laplacian mechanism are Δ/ϵ and 2Δ2/ϵ2, where Δ is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

We study the (nearly) optimal mechanisms in (ϵ, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ϵ and δ in utility and privacy analysis for histogram-like query functions, and show that the (ϵ, δ)-differential privacy is a framework not much more general than the (ϵ, 0)-differential privacy and (ϵ, δ)-differential privacy in the context of ℓ1and ℓ2cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ1and ℓ2cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (ϵ, δ) → (0, 0)). We conclude that in (ϵ, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/ϵ), (1/δ))) and Θ(min((1/ϵ2), (1/δ2))), respectively, in the high privacy regime.

Interactive querying of a database degrades the privacy level. In this paper we answer the fundamental question of characterizing the level of privacy degradation as a function of the number of adaptive interactions and the differential privacy levels maintained by the individual queries. Our solution is complete: the privacy degradation guarantee is true for every privacy mechanism, and further, we demonstrate a sequence of privacy mechanisms that do degrade in the characterized manner. The key innovation is the introduction of an operational interpretation (involving hypothesis testing) to differential privacy and the use of the corresponding data processing inequalities. Our result improves over the state of the art and has immediate applications to several problems studied in the literature.

We consider the single-unicast communication problem in a network with a delay constraint. For this setting, it has recently been shown that network coding offers an advantage over routing. We show that the existing upper bound in the literature on the capacity offered by network coding can be a factor of Θ(D) larger than the true capacity where D is the delay bound. In this work, we tighten this gap significantly to 8 log(D + 1) by proving a new upper bound. The key insight is a connection to a new traffic model that we call triangle-cast (or degraded multiple-unicast), for which we obtain a logarithmic flow-cut gap by suitably adapting the techniques from the approximation algorithms literature.

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Furthermore, we propose an interactive protocol for data exchange which increases the communication size in steps until the task is done and matches the performance of our lower bound. Our single-shot analysis applies to all discrete random variables and yields upper and lower bound of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general sequence such as mixture of IID random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for the IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

We study the problem of multi-party interactive function computation under differential privacy. In this setting, each party is interested in computing a function on its private bit and all the other parties' bits. The function to be computed can vary from one party to the other. Moreover, there could be a central observer who is interested in computing a separate function on all the parties' bits. Differential privacy ensures that there remains an uncertainty in any party's bit even when given the transcript of interactions and all other parties' bits. Performance at each party is measured via the accuracy of the function to be computed. We allow for an arbitrary cost metric to measure the distortion between the true and the computed function values. Our main result is the optimality of a simple non-interactive protocol: each party randomizes its bit (sufficiently) and shares the privatized version with the other parties. This optimality result is very general: it holds for all types of functions, heterogeneous privacy conditions on the parties, all types of cost metrics, and both average and worst-case (over the inputs) measures of accuracy.

Anonymous messaging platforms, such as Secret, Yik Yak and Whisper, have emerged as important social media for sharing one's thoughts without the fear of being judged by friends, family, or the public. Further, such anonymous platforms are crucial in nations with authoritarian governments; the right to free expression and sometimes the personal safety of the author of the message depend on anonymity. Whether for fear of judgment or personal endangerment, it is crucial to keep anonymous the identity of the user who initially posted a sensitive message. In this paper, we consider an adversary who observes a snapshot of the spread of a message at a certain time. Recent advances in rumor source detection shows that the existing messaging protocols are vulnerable against such an adversary. We introduce a novel messaging protocol, which we call adaptive diffusion, and show that it spreads the messages fast and achieves a perfect obfuscation of the source when the underlying contact network is an infinite regular tree: all users with the message are nearly equally likely to have been the origin of the message. Experiments on a sampled Facebook network show that it effectively hides the location of the source even when the graph is finite, irregular and has cycles.

We consider live-streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic connectivity guarantees, while structured trees have good connectivity but have proven hard to maintain under peer churn. We improve upon both approaches by presenting a novel distribution structure with a deterministic and distributed algorithm for maintenance under peer churn. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size.

We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334--347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185--204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lovász extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lovász extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285--301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303--6328] and we anticipate others in the future.

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this work we study the fundamental tradeoff between privacy and utility in differential privacy. We derive the optimal ε-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions, which can be viewed as a geometric mixture of uniform probability distributions. In the context of ℓ1and ℓ2utility functions, we show that the standard Laplacian mechanism, which has been widely used in the literature, is asymptotically optimal in the high privacy regime, while in the low privacy regime, the staircase mechanism performs exponentially better than the Laplacian mechanism. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

We propose a new coding scheme for interference alignment in a single hop fast fading wireless network with general message demands. For the X-Channel, the Degrees of Freedom (DoF) region achievable by the scheme is shown to touch a known outer-bound at several points. For multiple-multicast demands we show that the achievable region is at least half of the cut-set bound region. The key innovation in our scheme is the reduction of the vector space alignment problem to a combinatorial arrangement problem. Finally, we use the scheme to give a poly-logarithmic bound for the flow-cut gap in fast fading Gaussian wireless networks with multiple multicasts.

We study interference channels (IFCs) where the interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other using full-duplex radios. The interaction can come in two ways. First is through in-band interaction where sources and destinations can transmit and listen in the same channel simultaneously, enabling interaction. Second is through out-of-band interaction where destinations talk back to the sources on an out-of-band channel, which is possible from white-space channels. The flexibility afforded by the interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties,” i.e., insensitivity to the rationality or irrationality of channel parameters, small block lengths, and finite SNR operations. We show that, for several classes of IFCs, the interactive IA scheme can achieve the optimal degrees of freedom. In particular, we show a simple scheme (having a finite block length for channels having no diversity) for three-user and four-user IFCs with full-duplex radios to achieve the optimal degrees of freedom even after accounting for the cost of interaction. On the technical side, we show using a Gröbner basis argument that, in a general network potentially utilizing cooperation and feedback, the optimal degrees of freedom under linear schemes of a fixed block length is the same for channel coefficients with a probability of 1. Furthermore, a numerical method to estimate this value is also presented. These tools have potentially wider utility in studying other wireless networks as well.

The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks-our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.

A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast traffic (multiple sources communicating independent messages to multiple destinations): the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper, we extend the wireline result to the wireless context. In particular, we show the following meta-theorem: if for a given channel and its reciprocal channel, the cut-set bound is (approximately) achievable, then for multiple-unicast in a bidirected network comprised of such channels, the cut-set bound is (approximately) achievable within a logarithmic factor of the number of sources. The achievable scheme can be viewed as an instantiation of a simple layering principle: local physical-layer schemes combined with global routing. We use the reciprocity of the wireless channel critically in this result. We prove this result formally as a capacity approximation result for a variety of channel models, including general Gaussian networks under fast fading, networks comprised only of broadcast and MAC channels, and networks comprised of broadcast erasure channels with feedback. The capacity approximations we prove tend to have both an additive gap (power loss) and a multiplicative gap (degrees of freedom loss). The key engineering insight is that layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the locality over which physical-layer schemes should operate is carefully designed. Feedback is shown to play a critical role in enabling the separation between the physical and the network layers. The main technical contribution is the usage of polymatroidal network as a graphical model for analyzing the performance of complex wireless networks.

In this paper, a compress-and-forward scheme with backward decoding is presented for the unicast wireless relay network. The encoding at the source and relay is a generalization of the noisy network coding (NNC) scheme. While it achieves the same reliable data rate as NNC scheme, the backward decoding allows for a better decoding complexity as compared with the joint decoding of the NNC scheme. Characterizing the layered decoding scheme is shown to be equivalent to characterizing an information flow for the wireless network. A node-flow for a graph with bisubmodular capacity constraints is presented and a max-flow min-cut theorem is presented. This generalizes many well-known results of flows over capacity constrained graphs studied in computer science literature. The results for the unicast relay network are generalized to the network with multiple sources with independent messages intended for a single destination.

Energy harvesting sensor nodes are gaining popularity due to their ability to improve the network life time and are becoming a preferred choice supporting green communication. In this paper, we focus on communicating reliably over an additive white Gaussian noise channel using such an energy harvesting sensor node. An important part of this paper involves appropriate modeling of energy harvesting, as done via various practical architectures. Our main result is the characterization of the Shannon capacity of the communication system. The key technical challenge involves dealing with the dynamic (and stochastic) nature of the (quadratic) cost of the input to the channel. As a corollary, we find close connections between the capacity achieving energy management policies and the queueing theoretic throughput optimal policies.

The performance gain by allowing half-duplex source cooperation is studied for Gaussian interference channels. The source cooperation is in-band, meaning that each source can listen to the other source's transmission, but there is no independent (or orthogonal) channel between the sources. The half-duplex constraint supposes that at each time instant the sources can either transmit or listen, but not do both. Our main result is a characterization of the sum capacity when the cooperation is bidirectional and the channel gains are symmetric. With unidirectional cooperation, we essentially have a cognitive radio channel. By requiring the primary to achieve a rate close to its link capacity, the best possible rate for the secondary is characterized within a constant. Novel inner and outer bounds are derived as part of these characterizations.

We study interference channels (IFC) where interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other. The interaction can come in two ways: 1) for half-duplex radios, destinations can talk back to sources using either simultaneous out-of-band (white spaces) transmission or in-band half-duplex transmission; 2) for full-duplex radios, both sources and destinations can transmit and listen in the same channel simultaneously. The flexibility afforded by interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties”: insensitivity to the rationality or irrationality of channel parameters, small block lengths and finite SNR operations. We show that for several classes of interference channels the interactive interference alignment scheme can achieve the optimal degrees of freedom.

In the function computation problem, certain nodes of an undirected graph have access to independent data, while certain other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which the function computation is possible on a capacitated graph. We consider a general model of function computation, which we term as multi-session function multicasting. In this general model, there are K independent sessions sharing the communication infrastructure; in each session, a set of D destinations all want the same function of a group of S sources. This traffic model generalizes various well known traffic models like the classical model of function computation (K = 1, D = 1), multiple-unicasting (S = 1, D = 1) and multicasting (K = 1, S = 1). For this general model, we propose a simple achievable strategy in which the function is computed for each session using Steiner trees at a specific destination and then distributed to the other destinations also using Steiner trees. Thus, in our proposed strategy, Steiner trees play the dual role of computation trees and also that of multicasting trees. Our main result is that this achievable strategy is near optimal for multi-session function multicasting of a wide class of functions in undirected graphs. The key technical contribution involves relating algorithmic work on Steiner cuts in undirected graphs to the function computation problem.

We explore the benefit of feedback for physical layer interference management in wireless networks without centralized upper layer control mechanisms. Lack of coordination in the upper layer could make the interference experienced in the physical layer bursty. To understand how to harness such burstiness with feedback, we investigate a two-user bursty interference channel (IC), where the presence of interference is governed by a Bernoulli random state. We completely characterize the capacity region of the symmetric two-user linear deterministic bursty IC with feedback. The proposed two-phase scheme exploits feedback either for refining the previous interfered reception or for relaying additional information to the legitimate receiver of the other user. Matching outer bounds are derived by novel techniques that take the effect of delayed state information into account. We also use insights from the deterministic case to characterize the approximate symmetric capacity for the symmetric Gaussian bursty IC with feedback in the weak interference regime.

In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are near optimal for a wide class of function computation requirements even at multiple terminals in undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

Given training sequences generated by two distinct, but unknown, distributions on a common alphabet, we study the problem of determining whether a third sequence was generated according to the first or second distribution. To model sources such as natural language, for which the underlying distributions are difficult to learn from realistic amounts of data, we allow the alphabet size to grow and therefore the probability distributions to change with the block length. Our primary focus is the situation in which the underlying probabilities are all of the same order, and in this regime, we show that consistent classification is possible if and only if the alphabet grows subquadratically with the block length. We also show that some commonly used statistical tests are suboptimal in that they are consistent only if the alphabet grows sublinearly.

We consider all-cast and multicast flow problems where either all of the nodes or only a subset of the nodes may be in session. Traffic from each node in the session has to be sent to every other node in the session. If the session does not consist of all the nodes, the remaining nodes act as relays. The nodes are connected by undirected links whose capacities are independent and identically distributed random variables. We study the asymptotics of the capacity region (with network coding) in the limit of a large number of nodes, and show that the normalized sum rate converges to a constant almost surely. We then provide a decentralized push-pull algorithm that asymptotically achieves this normalized sum rate without network coding.

We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [20] and Hassin [15] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [10]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far as the authors are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks.

It has been shown recently that a simple layering principle - local physical-layer schemes combined with global routing - can achieve approximately optimal performance in wireless networks. However, this result depends heavily on the assumption of reciprocity of wireless networks, which may be violated due to asymmetric power constraints, directional antennas or frequency-duplexing. In this paper, we show that the approximate optimality continues to hold even for wireless networks modeled as directed graphs as long as there is a symmetric demand constraint: every demand from source sito sink tiat rate Rihas a counterpart demand from source node tito sink node siat the same rate. This models several practical scenarios including voice calls, video calls, and interactive gaming. We prove this result in the context of several channel models for which good local schemes exist. The key technical contributions are an outer bound based on a Generalized Network Sharing bound for wireless networks and an achievable strategy based on a connection to polymatroidal networks.

We consider the problem of multiple unicast in wireline networks. Edge-cut based bounds which are simple bounds on the rates achievable by routing flow are not in general, fundamental, i.e. they are not outer bounds on the capacity region. It has been observed that when the problem has some kind of symmetry involved, then flows and edge-cut based bounds are `close', i.e. within a constant or poly-logarithmic factor of each other. In this paper, we make the observation that in these very cases, such edge-cut based bounds are actually `close' to fundamental yielding an approximate characterization of the capacity region for these problems. We demonstrate this in the case of k-unicast in undirected networks, k-pair unicast in directed networks with symmetric demands i.e. for every source communicating to a destination at a certain rate, the destination communicates an independent message back to the source at the same rate, and sum-rate of k-groupcast in directed networks, i.e. a group of nodes, each of which has an independent message for every other node in the group. We place our work in context of existing results to suggest a meta-theorem: if there is inherent symmetry either in the network connectivity or in the traffic pattern, then edge-cut bounds are near-fundamental and flows approximately achieve capacity.

We consider multicast flow problems where either all of the nodes or only a subset of the nodes may be in session. Traffic from each node in the session has to be sent to every other node in the session. If the session does not consist of all the nodes, the remaining nodes act as relays. The nodes are connected by undirected edges whose capacities are independent and identically distributed random variables. We study the asymptotics of the capacity region (with network coding) in the limit of a large number of nodes, and show that the normalized sum rate converges to a constant almost surely. We then provide a decentralized push-pull algorithm that asymptotically achieves this normalized sum rate.

Unlike their cellular counterparts, Wi-Fi networks do not have the luxury of a dedicated control plane that is decoupled from the data plane. Consequently, Wi-Fi struggles to provide many of the capabilities that are taken for granted in cellular networks, including efficient and fair resource allocation, QoS and handoffs. The reason for the lack of a control plane with designated spectrum is that it would impose significant overhead. This is at odds with Wi-Fi's goal of providing a simple, plug-and-play network.

We study a wireless broadcast network, where a single source reliably communicates independent messages to multiple destinations, with the potential aid of relays and cooperation between destinations. The wireless nature of the medium is captured by the broadcast nature of transmissions as well as the superposition of transmitted signals plus independent Gaussian noise at the received signal at any radio. We propose a scheme that can achieve rate tuples within a constant gap away from the cut-set bound, where the constant is independent of channel coefficients and power constraints. First, for a deterministic broadcast network, we propose a new coding scheme, constructed by adopting a “receiver-centric” viewpoint, that uses quantize-and-forward relaying as an inner code concatenated with an outer Marton code for the induced deterministic broadcast channel. This scheme is shown to achieve the cut-set bound evaluated with product form distributions. This result is then lifted to the Gaussian network by using a deterministic network called the discrete superposition network as a formal quantization interface. This two-stage construction circumvents the difficulty involved in working with a vector nonlinear non-Gaussian broadcast channel that arises if we construct a similar scheme directly for the Gaussian network.

Network life time maximization is becoming an important design goal in wireless sensor networks. Energy harvesting has recently become a preferred choice for achieving this goal as it provides near perpetual operation. We study such a sensor node with an energy harvesting source and compare various architectures by which the harvested energy is used. We find its Shannon capacity when it is transmitting its observations over a fading AWGN channel with perfect/no channel state information provided at the transmitter. We obtain an achievable rate when there are inefficiencies in energy storage and the capacity when energy is spent in activities other than transmission.

A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast: the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. Wireless channels differ from wireline ones in two primary ways: the signal out of a transmitting node is broadcast and the signals at a receiving node superpose. In this paper we focus on “extending” the wireline result to the wireless context, by separately considering the broadcast and superposition constraints. Our main result is the approximate optimality of a simple layering principle: local physical-layer schemes combined with global routing. We show this in the context of both Gaussian networks and packet erasure networks. The key technical contribution is an approximation of min cut in a bidirected graph with submodular constraints on the edge capacities by max flow.

We study a wireless broadcast-cum-multicast network, where a single source reliably communicates independent messages to multiple destinations, with the aid of relays. In addition, we assume there are nodes that demand all the messages at the source. We propose a compress-and-forward scheme that can achieve rates within a constant gap away from the cut-set bound. The proposed scheme operates in two steps: the inner code induces a broadcast channel with sufficient mutual information between the source and the destinations, and the outer code is basically a Marton code for broadcast channels. The inner code is constructed by lifting a scheme designed for a corresponding discrete superposition network.

A classical result in undirected wireline networks is the approximate optimality of routing (flow) for multiple-unicast: the min-cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper we focus on “extending” this result to the wireless context. Our main result is the approximate optimality of a simple layering principle: local physical-layer schemes combined with global routing. We show this in the context of wireless networks, in which links are either absent or undergo i.i.d. fast fading. We also show an approximation result on the degrees-of-freedom, when the channels are fixed, but are chosen from a continuous ensemble. The key technical contribution is an approximation of min-cut in a bidirected graph with submodular constraints on the edge capacities by max flow.

We study a wireless relay network, with a single source and a single destination. Our main result is to show that an appropriate compress-and-forward scheme supports essentially the same reliable data rate as the quantize-map-and-forward and noisy network coding schemes [1], [2]; thus, it is approximately optimal - in the sense the data rate is a universal constant away from the cut-set upper bound. We characterize the compress-and-forward scheme through an abstract flow formulation, a generalization of flow on linking systems. This characterization allows for efficient computation of the minimal amount of information that has to flow through each node in the network.

Sensor nodes with energy harvesting sources are gaining popularity due to their ability to improve the network life time and are becoming a preferred choice supporting `green communication'. We study such a sensor node with an energy harvesting source and compare various architectures by which the harvested energy is used. We find its Shannon capacity when it is transmitting its observations over an AWGN channel and show that the capacity achieving energy management policies are related to the throughput optimal policies. We also obtain the capacity when energy conserving sleep-wake modes are supported and an achievable rate for the system with inefficiencies in energy storage.

In this paper, the role of cooperation in managing interference-a fundamental feature of the wireless channel-is investigated by studying the two-user Gaussian interference channel where the source nodes can both transmit and receive in full duplex. The sum capacity of this channel is obtained within a gap of a constant number of bits. The coding scheme used builds up on the superposition scheme of Han and Kobayashi for the two-user interference channel without cooperation. New upperbounds on the sum capacity are also derived. The same coding scheme is shown to obtain the sum capacity of the symmetric two-user Gaussian interference channel with noiseless feedback within a constant gap.

Interference is a fundamental feature of the wireless channel. To better understand the role of cooperation in interference management, the two-user Gaussian interference channel where the destination nodes can cooperate by virtue of being able to both transmit and receive is studied. The sum capacity of this channel is characterized up to a constant number of bits. The coding scheme employed builds up on the superposition scheme of Han and Kobayashi for two-user interference channels without cooperation. New upperbounds to the sum capacity are also derived.

Diversity-multiplexing tradeoff (DMT) is a coarse high SNR approximation of the fundamental tradeoff between data rate and reliability in a slow fading channel. In this paper, we characterize the fundamental DMT of the two-user single antenna Gaussian interference channel. We show that the class of multilevel superposition coding schemes universally achieves (for all fading statistics) the DMT for the two-user interference channel. For the special case of symmetric DMT, when the two users have identical rate and diversity gain requirements, we characterize the DMT achieved by the Han-Kobayashi scheme, which corresponds to two level superposition coding.

We address the problem of estimating the probability of an observed string that is drawn i.i.d. from an unknown distribution. Motivated by models of natural language, we consider the regime in which the length of the observed string and the size of the underlying alphabet are comparably large. In this regime, the maximum likelihood distribution tends to overestimate the probability of the observed letters, so the Good–Turing probability estimator is typically used instead. We show that when used to estimate the sequence probability, the Good–Turing estimator is not consistent in this regime. We then introduce a novel sequence probability estimator that is consistent. This estimator also yields consistent estimators for other quantities of interest and a consistent universal classifier.

Given training sequences generated by two distinct, but unknown distributions sharing a common alphabet, we seek a classifier that can correctly decide whether a third test sequence is generated by the first or second distribution using only the training data. To model `limited learning' we allow the alphabet size to grow and therefore probability distributions to change with the blocklength. We prove that a natural choice, namely a generalized likelihood ratio test, is universally consistent (has a probability of error tending to zero with the blocklength for all underlying distributions) when the alphabet size is sub-linear in the blocklength, but inconsistent for linear alphabet growth. For up-to quadratic alphabet growth, in a regime where all probabilities are of the same order, we prove the universally consistency of a new test and show there are no such tests when the alphabet grows quadratically or faster.

We study the two-user interference channel where the source nodes may transmit and receive in half-duplex while the destinations only receive as usual. Depending on the sources, the channel can be in one of three modes: A) both sources transmit, B) source 1 transmits while source 2 receives, and C) source 2 transmits and source 1 receives. This allows a limited form of cooperation between the sources. In this paper, we focus on the corresponding symmetric linear deterministic channel and derive its sum capacity. We consider a scheme which, by operating in modes B and C, transforms mode A into a virtual two-user interference channel with rate-limited bit pipes between the two source nodes and from each source node to the destination node it causes interference to. For the virtual channel so created, we propose a generalization of the superposition coding scheme of Han-Kobayashi to take advantage of the bit pipes. Finally, we derive matching upperbounds to show that the performance of the composite scheme is indeed optimal for the original channel.

Multiuser diversity is achieved by maximum C/I scheduler in both fast and slow fading scenarios. However, fairness among multiple users is not guaranteed in slow fading channel because time and frequency resource are always occupied by the user with largest signal to interference and noise ratio(SINR). Opportunistic beamforming using dumb antennas is a multiple antennas transmit technique to increase the fluctuation rate and dynamic range of effective channel coefficients in slow fading environment. In this paper, we propose a method to improve the fairness of maximum C/I scheduler with the technique of dumb antennas. The theoretical analysis of users' scheduling probability shows that the fairness of maximum C/I scheduler can be greatly improved by dumb antennas in slow fading channels without significant loss in cell spectrum efficiency. The engineering issues of its application in the downlink transmission of 3GPP LTE system are discussed. The numerical results of simulation with practical LTE configurations and assumptions also verify our proposal.

We study two building-block models of interference-limited wireless networks, motivated by the problem of joint Peer-to-Peer and Wide Area Network design. In the first case, a single “long-range” transmitter interferes with multiple parallel “short-range” transmissions, and, in the second case, multiple short-range transmitters interfere with a single long-range receiver. We identify the maximal degree-of-freedom region of the former network and show that multilevel superposition coding by the long-range transmitter performs optimally. Moreover, a simple power control strategy, performed by the long-range transmitter, achieves a region that is within one bit of the capacity region, under certain channel conditions. For the latter network, we show that short-range transmitter power control is degree-of-freedom optimal under certain channel conditions.

Jointly Gaussian memoryless sources are observed atNdistinct terminals. The goal is to efficiently encode the observations in a distributed fashion so as to enable reconstruction of any one of the observations, say the first one, at the decoder subject to a quadratic fidelity criterion. Our main result is aprecisecharacterization of the rate-distortion region when the covariance matrix of the sources satisfies a ¿tree-structure¿ condition. In this situation, a natural analog-digital separation scheme optimally trades off the distributed quantization rate tuples and the distortion in the reconstruction: each encoder consists of a point-to-point Gaussian vector quantizer followed by a Slepian-Wolf binning encoder. We also provide a partial converse that suggests that the tree-structure condition is fundamental.

Interference is a central feature of the wireless channel. However, in many cases, the interferer's activity can be bursty and it is overly pessimistic to assume that interference is always present. In this paper, we use a degraded message set formulation of the two-user interference channel to study the statistical gains that can be harnessed from bursty interference. We consider a linear deterministic model of the Gaussian interference channel and characterize the degraded message set capacity region.

We consider a two-user interference channel where the source/destination nodes can cooperate with each other by virtue of being able to both transmit and receive. For the full-duplex mode of operation, we characterize the sum capacity of a linear deterministic channel exactly, and that of the Gaussian channel up to a constant number of bits. This reveals a reciprocity between the cases where the sources cooperate and the destinations cooperate. The main contributions are novel strategies and new upper bounds.

Diversity-multiplexing tradeoff (DMT) is a coarse high SNR approximation of the fundamental tradeoff between data rate and reliability in a slow fading channel. In this paper, we characterize the fundamental DMT of the two-user single antenna Gaussian interference channel. We show that the class of multilevel superposition coding schemes universally achieves (for all fading statistics) the DMT for the two-user interference channel. For the special case of symmetric DMT, when the two users have identical rate and diversity gain requirements, we characterize the DMT achieved by the Han-Kobayashi scheme, which corresponds to two level superposition coding.

Interference is a central feature of wireless communication. In many scenarios, interference is bursty: interfering wireless links come and go. Designing the system assuming interference to be always present is very conservative. In this paper, we take a fundamental information theoretic stand point and address the issue of statistical gain associated with bursty interference in the context of a pair of unicast interfering wireless links. Modeling the problem as a ldquodegraded message setrdquo two user Gaussian interference channel, we approximately characterize the symmetric capacity region. Our results demonstrate the fundamental existence of three regimes: one where treating interference as always there is without loss of optimality, another where one can harness as well as if interference was never there and a third where the performance is in between these two regimes.

The linear deterministic model has been used recently to get a first order understanding of many wireless communication network problems. In many of these cases, it has been pointed out that the capacity regions of the network and its reciprocal (where the communication links are reversed and the roles of the sources and the destinations are swapped) are the same. In this paper, we consider a linear deterministic communication network with multiple unicast information flows. For this model and under the restriction to the class of linear coding, we show that the rate regions for a network and its reciprocal are the same. This can be viewed as a generalization of the linear reversibility of wireline networks, already known in the network coding literature.

In this paper, we consider a communication scenario in which the primary and the cognitive radios wish to communicate to different receivers, subject to mutual interference. In the model that we use, the cognitive radio has noncausal knowledge of the primary radio's codeword. We characterize the largest rate at which the cognitive radio can reliably communicate under the constraint that 1)no rate degradationis created for the primary user, and 2) the primary receiver uses asingle-user decoderjust as it would in the absence of the cognitive radio. The result holds in a “low-interference” regime in which the cognitive radio is closer to its receiver than to the primary receiver. In this regime, our results are subsumed by the results derived in a concurrent and independent work (Wu, 2007). We also demonstrate that, in a “high-interference” regime, multiuser decoding at the primary receiver is optimal from the standpoint of maximal jointly achievable rates for the primary and cognitive users.

We introduce the two-user finite state compound interference channel. The main contributions involve both novel inner and outer bounds. For the Gaussian case, we characterize its capacity region to within one bit. The inner bound is multilevel superposition coding but the decoding of the levels is opportunistic, depending on the channel state. The genie aided outer bound is motivated by the typical error events of the achievable scheme.

This book provides a thorough coverage of wireless communication fundamentals, with emphasis on information-theoretic concepts. Some of the topics covered include: mathematical models for the physical channel; digital communication and the concept of diversity transmission for fading channels; cellular systems; capacity of wireless channels; multi-user capacity and opportunistic communication; and an extensive treatment of MIMO systems. The list of references is extensive and the index has been prepared with considerable care. The book would make an ideal resource for graduate students seeking a first exposure to the field.

The problem of L multiple descriptions of a stationary and ergodic Gaussian source with two levels of receivers is investigated. Each of the first-level receivers receive (an arbitrary subset) k of the L descriptions,(k

The capacity region of a compound multiple-antenna broadcast channel is characterized when the users exhibit a certain degradedness order. The channel under consideration has two users, each user has a finite set of possible realizations. The transmitter transmits two messages, one for each user, in such a manner that regardless of the actual realizations, both users will be able to decode their messages correctly. An alternative view of this channel is that of a broadcast channel with two common messages, each common message is intended to a different set of users. The degradedness order between the two sets of realizations/users is defined through an additional, fictitious, user whose channel is degraded with respect to all realizations/users from one set while all realizations/users from the other set are degraded with respect to him.

We introduce the two user finite state compound Gaussian interference channel and characterize its capacity region to within one bit. The main contributions involve both novel inner and outer bounds. The inner bound is multilevel superposition coding but the decoding of the levels is opportunistic, depending on the channel state. The genie aided outer bound is motivated by the typical error events of the achievable scheme.

We determine the rate region of the quadratic Gaussian two-encoder source-coding problem. This rate region is achieved by a simple architecture that separates the analog and digital aspects of the compression. Furthermore, this architecture requires higher rates to send a Gaussian source than it does to send any other source with the same covariance. Our techniques can also be used to determine the sum-rate of some generalizations of this classical problem. Our approach involves coupling the problem to a quadratic Gaussian ldquoCEO problem.rdquo

We consider the problem of estimating the probability of an observed string drawn i.i.d. from an unknown distribution. The key feature of our study is that the length of the observed string is assumed to be of the same order as the size of the underlying alphabet. In this setting, many letters are unseen and the empirical distribution tends to overestimate the probability of the observed letters. To overcome this problem, the traditional approach to probability estimation is to use the classical Good-Turing estimator. We introduce a natural scaling model and use it to show that the Good-Turing sequence probability estimator is not consistent. We then introduce a novel sequence probability estimator that is indeed consistent under the natural scaling model.

The capacity region of a compound multi-antenna broadcast channel is characterized when the users exhibit a certain degradedness order. For this purpose, we bring to bear a new extremal inequality for information theory and utilize a channel enhancement technique.

We prove a new extremal inequality, motivated by the vector Gaussian broadcast channel and the distributed source coding with a single quadratic distortion constraint problems. As a corollary, this inequality yields a generalization of the classical entropy-power inequality (EPI). As another corollary, this inequality sheds insight into maximizing the differential entropy of the sum of two dependent random variables

T multiple descriptions of a vector Gaussian source for individual and central receivers are investigated. The sum rate of the descriptions with covariance distortion measure constraints, in a positive semidefinite ordering, is exactly characterized. For two descriptions, the entire rate region is characterized. The key component of the solution is a novel information-theoretic inequality that is used to lower-bound the achievable multiple description rates. Jointly Gaussian descriptions are optimal in achieving the limiting rates. We also show the robustness of this description scheme: the distortions achieved are no larger when used to describe any non-Gaussian source with the same covariance matrix.

We study throughput scaling in an ad-hoc wireless network where the communication domain is divided into overlapping neighborhoods and n mobile nodes are restricted to move within their assigned neighborhood. In our model, when a node is located in a region not shared with any other neighborhood, it transmits to nodes of its own neighborhood only; when it is in an area that overlaps with another neighborhood, it transmits to nodes of the overlapping neighborhood. Communication between source-destination pairs is subject to interference from other nodes. By adopting a deterministic approach, we obtain an achievable throughput which is a function of properties of the node locations and neighborhood dimensions. As special cases of our neighborhood model, the results of P. Gupta and P.R. Kumar (2000) and M. Grossglauser and D. Tse (2002) can be recovered. We then study the case of random placement of nodes with nalphaneighborhoods, where 0 les alpha les 1, and achieve a throughput of Omega (n1-alpha/2). Hence our model captures every order of growth for the throughput, encompassing the results from both P. Gupta and P.R. Kumar (2000) and M. Grossglauser and D. Tse (2002) as extreme situations

Cognitive radios have been proposed as a means to implement efficient reuse of the licensed spectrum. The key feature of a cognitive radio is its ability to recognize the primary (licensed) user and adapt its communication strategy to minimize the interference that it generates. We consider a communication scenario in which the primary and the cognitive user wish to communicate to different receivers, subject to mutual interference. Modeling the cognitive radio as a transmitter with side-information about the primary transmission, we characterize the largest rate at which the cognitive radio can reliably communicate under the constraint that (i) no interference is created for the primary user, and (ii) the primary encoder-decoder pair is oblivious to the presence of the cognitive radio.

We prove a new extremal inequality, motivated by the vector Gaussian broadcast channel and the distributed source coding with a single quadratic distortion constraint problem. As a corollary, this inequality yields a generalization of the classical vector entropy-power inequality (EPI). As another corollary, this inequality sheds insight into maximizing differential entropy of a sum of jointly distributed random variables, generalizing a classical result of Cover and Zhang

We determine the rate region of the quadratic Gaussian two-encoder source-coding problem with separate distortion constraints. This region is achieved by a simple architecture that separates the analog and digital aspects of the compression. Furthermore, this architecture requires higher rates to send a Gaussian source than it does to send any other source with the same covariance. The proof technique can be used to partially solve problems with more than two encoders or more general distortion constraints

We consider the problem of estimating the total probability of all symbols that appear with a given frequency in a string of i.i.d. random variables with unknown distribution. We focus on the regime in which the block length is large yet no symbol appears frequently in the string. This is accomplished by allowing the distribution to change with the block length. Under a natural convergence assumption on the sequence of underlying distributions, we show that the total probabilities converge to a deterministic limit, which we characterize. We then show that the good-turing total probability estimator is strongly consistent

L multiple descriptions of a vector Gaussian source for individual and central receivers are investigated. The sum rate of the descriptions with covariance distortion measure constraints, in a positive semidefinite ordering, is exactly characterised. For two descriptions, the entire rate region is characterized. Jointly Gaussian descriptions are optimal in achieving the limiting rates. The key component of the solution is a novel information-theoretic inequality that is used to lower bound the achievable multiple description rates

In this correspondence, we study the capacity region of a general wireless network by deriving fundamental upper bounds on a class of linear functionals of the rate tuples at which joint reliable communication can take place. The widely studied transport capacity is a specific linear functional: the coefficient of the rate between a pair of nodes is equal to the Euclidean distance between them. The upper bound on the linear functionals of the capacity region is used to derive upper bounds to scaling laws for generalized transport capacity: the coefficient of the rate between a pair of nodes is equal to some arbitrary function of the Euclidean distance between them, for a class of minimum distance networks. This upper bound to the scaling law meets that achievable by multihop communication over these networks for a wide class of channel conditions; this shows the optimality, in the scaling-law sense, of multihop communication when studying generalized transport capacity of wireless networks.

A simple scheme that achieves the capacity and the reliability function of the wideband Costa dirty-paper channel is proposed. The scheme can be interpreted as an opportunistic version of pulse position modulation (PPM). This interpretation suggests a natural generalization of the scheme which we show to achieve the capacity per unit cost of Gel'fand-Pinsker channels with a zero-cost input letter.

Performance of reliable communication over a coherent slow-fading multiple-input multiple-output (MIMO) channel at high signal-to-noise ratio (SNR) is succinctly captured as a fundamental tradeoff between diversity and multiplexing gains. This paper studies the problem of designing codes that optimally tradeoff the diversity and multiplexing gains. The main contribution is a precise characterization of codes that are universally tradeoff-optimal, i.e., they optimally tradeoff the diversity and multiplexing gains for every statistical characterization of the fading channel. This characterization is referred to as approximate universality; the approximation is in the connection between error probability and outage capacity with diversity and multiplexing gains, respectively. The characterization of approximate universality is then used to construct new coding schemes as well as to show optimality of several schemes proposed in the space-time coding literature.

In this paper, an alternative model of restricted mobility by considering nodes confined to overlapping neighborhoods is presented. The throughput per source-destination (S-D) pair can be kept constant as the number of nodes increases. For arbitrary assignment of nodes to neighborhoods, achievable orders of throughput per S-D pair as a function of properties of the node locations and neighborhood dimensions is obtained. The succession of neighborhoods that a packet crosses from sender to destination is predetermined by a routing algorithm resulting from establishing a correspondence between the traffic pattern through the neighborhoods in the wireless network and a 2-D mesh network of processing units.

This paper considers reliable communication over a parallel (correlated) fading channel for short periods of time. We derive a code design criterion by taking a compound channel viewpoint of the outage capacity of the channel. Motivated by the criterion, we show existence of simple codes that achieve the optimal diversity-multiplexing tradeoff curve, introduced recently in (Zheng, L et al., 2003), simultaneously for every correlated parallel channel. We demonstrate a code with simple encoding and decoding for a parallel channel with two diversity branches. The codes for the parallel channel can be used on a correlated MIMO channel by using the DBLAST architecture to simultaneously achieve the diversity-multiplexing tradeoff curve for arbitrary fading channels.

In this paper, the meaning of duality in terms of the coding operations and the corresponding performance measures are examined. In this paper, operational duality to the channel and source coding problems with side information are extended. A class of deterministic maximal binning schemes is constructed. Each bin corresponds to a maximal channel code and the collection of the codewords in all the bins forms a maximal channel code. The construction of the binning scheme from the individual channel codes is greedy and provides an alternative proof of the coding theorem for the two side information problems.

We present coding schemes that achieve the diversity-multiplexing tradeoff for Rayleigh fading channels with one or two receive antennas and arbitrary number of transmit antennas. Codes designed for a parallel channel are the key constituents along with the D-BLAST architecture. We show that the joint ML receiver for D-BLAST outperforms the traditional MMSE with successive cancellation receiver.

We derive upper bounds on the transport capacity of wireless networks. The bounds obtained are solely dependent on the geographic locations and power constraints of the nodes. As a result of this derivation, we are able to conclude the optimality, in the sense of scaling of transport capacity with the number of nodes, of a multihop communication strategy for a class of network topologies.

We address the problem of how throughput in a wireless network scales as the number of users grows. Following the model of Gupta and Kumar, we consider n identical nodes placed in a fixed area. Pairs of transmitters and receivers wish to communicate but are subject to interference from other nodes. Throughput is measured in bit-meters per second. We provide a very elementary deterministic approach that gives achievability results in terms of three key properties of the node locations. As a special case, we obtain /spl Omega/(/spl radic/n) throughput for a general class of network configurations in a fixed area. Results for random node locations in a fixed area can also be derived as special cases of the general result by verifying the growth rate of three parameters. For example, as a simple corollary of our result we obtain a stronger (almost sure) version of the /spl radic/n//spl radic/(logn) throughput for random node locations in a fixed area obtained by Gupta and Kumar. Results for some other interesting non-independent and identically distributed (i.i.d.) node distributions are also provided.

In a point-to-point wireless fading channel, multiple transmit and receive antennas can be used to improve the reliability of reception (diversity gain) or increase the rate of communication for a fixed reliability level (multiplexing gain). In a multiple-access situation, multiple receive antennas can also be used to spatially separate signals from different users (multiple-access gain). Recent work has characterized the fundamental tradeoff between diversity and multiplexing gains in the point-to-point scenario. In this paper, we extend the results to a multiple-access fading channel. Our results characterize the fundamental tradeoff between the three types of gain and provide insights on the capabilities of multiple antennas in a network context.

We characterize the sum capacity of the vector Gaussian broadcast channel by showing that the existing inner bound of Marton and the existing upper bound of Sato are tight for this channel. We exploit an intimate four-way connection between the vector broadcast channel, the corresponding point-to-point channel (where the receivers can cooperate), the multiple-access channel (MAC) (where the role of transmitters and receivers are reversed), and the corresponding point-to-point channel (where the transmitters can cooperate).

We consider direct sequence code division multiple access (DS-CDMA), modeling interference from users communicating with neighboring base stations by additive colored noise. We consider two types of receiver structures: first we consider the information-theoretically optimal receiver and use the sum capacity of the channel as our performance measure. Second, we consider the linear minimum mean square error (LMMSE) receiver and use the signal-to-interference ratio (SIR) of the estimate of the symbol transmitted as our performance measure. Our main result is a constructive characterization of the possible performance in both these scenarios. A central contribution of this characterization is the derivation of a qualitative feature of the optimal performance measure in both the scenarios studied. We show that the sum capacity is a saddle function: it is convex in the additive noise covariances and concave in the user received powers. In the linear receiver case, we show that the mini average power required to meet a set of target performance requirements of the users is a saddle function: it is convex in the additive noise covariances and concave in the set of performance requirements.

Multiuser diversity is a form of diversity inherent in a wireless network, provided by independent time-varying channels across the different users. The diversity benefit is exploited by tracking the channel fluctuations of the users and scheduling transmissions to users when their instantaneous channel quality is near the peak. The diversity gain increases with the dynamic range of the fluctuations and is thus limited in environments with little scattering and/or slow fading. In such environments, we propose the use of multiple transmit antennas to induce large and fast channel fluctuations so that multiuser diversity can still be exploited. The scheme can be interpreted as opportunistic beamforming and we show that true beamforming gains can be achieved when there are sufficient users, even though very limited channel feedback is needed. Furthermore, in a cellular system, the scheme plays an additional role of opportunistic nulling of the interference created on users of adjacent cells. We discuss the design implications of implementing. this scheme in a complete wireless system.

Dynamic resource allocation is an important means to increase the sum capacity of fading multiple-access channels (MACs). In this paper, we consider vector multi-access channels (channels where each user has multiple degrees of freedom) and study the effect of power allocation as a function of the channel state on the sum capacity (or spectral efficiency) defined as the maximum sum of rates of users per unit degree of freedom at which the users can jointly transmit reliably, in an information-theoretic sense, assuming random directions of received signal. Direct-sequence code-division multiple-access (DS-CDMA) channels and MACs with multiple antennas at the receiver are two systems that fall under the model. Our main result is the identification of a simple dynamic power-allocation scheme that is optimal in a large system, i.e., with a large number of users and a correspondingly large number of degrees of freedom. A key feature of this policy is that, for any user, it depends on the instantaneous amplitude of channel state of that user alone and the structure of the policy is "water-filling." In the contest of DS-CDMA and in the special case of no fading, the asymptotically optimal power policy of water-filling simplifies to constant power allocation over all realizations of signature sequences; this result verifies the conjecture made in Verdu and Shamai (1999). We study the behavior of the asymptotically optimal water-filling policy in various regimes of number of users per unit degree of freedom and signal-to-noise ratio (SNR). We also generalize this result to multiple classes, i.e., the situation when users in different classes have different average power constraints.

The sum capacity of a multiuser synchronous CDMA system is completely characterized in the general case of asymmetric user power constraints-this solves the open problem posed by Rupf and Massey (see ibid., vol.40, p.1261-6, 1994) which had solved the equal power constraint case. We identify the signature sequences with real components that achieve sum capacity and indicate a simple recursive algorithm to construct them.

There has been intense effort in the past decade to develop multiuser receiver structures which mitigate interference between users in spread-spectrum systems. While much of this research is performed at the physical layer, the appropriate power control and choice of signature sequences in conjunction with multiuser receivers and the resulting network user capacity is not well understood. In this paper we will focus on a single cell and consider both the uplink and downlink scenarios and assume a synchronous CDMA (S-CDMA) system. We characterize the user capacity of a single cell with the optimal linear receiver (MMSE receiver). The user capacity of the system is the maximum number of users per unit processing gain admissible in the system such that each user has its quality-of-service (QoS) requirement (expressed in terms of its desired signal-to-interference ratio) met. This characterization allows one to describe the user capacity through a simple effective bandwidth characterization: users are allowed in the system if and only if the sum of their effective bandwidths is less than the processing gain of the system. The effective bandwidth of each user is a simple monotonic function of its QoS requirement. We identify the optimal signature sequences and power control strategies so that the users meet their QoS requirement. The optimality is in the sense of minimizing the sum of allocated powers. It turns out that with this optimal allocation of signature sequences and powers, the linear MMSE receiver is just the corresponding matched filter for each user. We also characterize the effect of transmit power constraints on the user capacity.

Studies the global asymptotic stability of a class of fuzzy systems. It demonstrates the equivalence of stability properties of fuzzy systems and linear time invariant (LTI) switching systems. A necessary and sufficient condition for the stability of such systems are given, and it is shown that under the sufficient condition, a common Lyapunov function exists for the LTI subsystems. A particular case when the system matrices can be simultaneously transformed to normal matrices is shown to correspond to the existence of a common quadratic Lyapunov function. A constructive procedure to check the possibility of simultaneous transformation to normal matrices is provided.

The addition of programmable logic to RISC machines has the potential of exploiting the inherent parallelism of hardware to speedup an application. The authors study the effect of adding a programmable accelerator to DLX, a RISC prototype. They build this model and parameterize the communication overhead between the processor and programmable unit and logic/routing delays inside the programmable unit. They use simulation to evaluate the performance of this model, parameterized by communication overhead and logic delays, by comparing it with the baseline DLX architecture on some sample problems. The methodology is useful in studying the relative importance of the parameters and in projecting the performance of the system, if the programmable logic were to be implemented inside the processor.