BZPEERPapers, people, evidence and research paths
Menu

Discover

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

Research tools

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

Network

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

Opportunities

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

Account

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

Source author record

Pramod Viswanath

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

ResearcherUnclaimed source record
Information Theorymath.ITCryptography and SecurityMachine LearningData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingNetworking and Internet ArchitectureComputation and LanguageSocial and Information NetworksArtificial IntelligenceComputational ComplexityComputer Science and Game TheoryDiscrete Mathematicseess.SP

Catalog footprint

What is connected

40works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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

Building this map preview

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

Published work

40 published item(s)

preprint2022arXiv

Minotaur: Multi-Resource Blockchain Consensus

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. In this work, we put forth Minotaur, a multi-resource blockchain consensus protocol that combines proof-of-work (PoW) and proof-of-stake (PoS), and we prove it optimally fungible. At the core of our design, Minotaur operates in epochs while continuously sampling the active computational power to provide a fair exchange between the two resources, work and stake. Further, we demonstrate the ability of Minotaur to handle a higher degree of work fluctuation as compared to the Bitcoin blockchain; we also generalize Minotaur to any number of resources. We demonstrate the simplicity of Minotaur via implementing a full stack client in Rust (available open source). We use the client to test the robustness of Minotaur to variable mining power and combined work/stake attacks and demonstrate concrete empirical evidence towards the suitability of Minotaur to serve as the consensus layer of a real-world blockchain.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Bootstrapping of PoW Blockchains

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. In this paper, we propose Advocate, a new bootstrapping methodology, which achieves two main results: (a) optimal liveness and low latency under a super-majority adversary for the Nakamoto longest chain protocol and (b) immediate black-box generalization to a variety of parallel-chain based scaling architectures, including OHIE and Prism. We demonstrate via a full-stack implementation the robustness of Advocate under a 90% adversarial majority.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

ACeD: Scalable Data Availability Oracle

A popular method in practice offloads computation and storage in blockchains by relying on committing only hashes of off-chain data into the blockchain. This mechanism is acknowledged to be vulnerable to a stalling attack: the blocks corresponding to the committed hashes may be unavailable at any honest node. The straightforward solution of broadcasting all blocks to the entire network sidesteps this data availability attack, but it is not scalable. In this paper, we propose ACeD, a scalable solution to this data availability problem with $O(1)$ communication efficiency, the first to the best of our knowledge. The key innovation is a new protocol that requires each of the $N$ nodes to receive only $O(1/N)$ of the block, such that the data is guaranteed to be available in a distributed manner in the network. Our solution creatively integrates coding-theoretic designs inside of Merkle tree commitments to guarantee efficient and tamper-proof reconstruction; this solution is distinct from Asynchronous Verifiable Information Dispersal (in guaranteeing efficient proofs of malformed coding) and Coded Merkle Tree (which only provides guarantees for random corruption as opposed to our guarantees for worst-case corruption). We implement ACeD with full functionality in 6000 lines of Rust code, integrate the functionality as a smart contract into Ethereum via a high-performance implementation demonstrating up to 10,000 transactions per second in throughput and 6000x reduction in gas cost on the Ethereum testnet Kovan.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Reed-Muller Subcodes: Machine Learning-Aided Design of Efficient Soft Recursive Decoding

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 in this paper, 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 \textit{good} sets of projections in the sense of minimizing 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Deepcode and Modulo-SK are Designed for Different Settings

We respond to [1] which claimed that "Modulo-SK scheme outperforms Deepcode [2]". We demonstrate that this statement is not true: the two schemes are designed and evaluated for entirely different settings. DeepCode is designed and evaluated for the AWGN channel with (potentially delayed) uncoded output feedback. Modulo-SK is evaluated on the AWGN channel with coded feedback and unit delay. [1] also claimed an implementation of Schalkwijk and Kailath (SK) [3] which was numerically stable for any number of information bits and iterations. However, we observe that while their implementation does marginally improve over ours, it also suffers from a fundamental issue with precision. Finally, we show that Deepcode dominates the optimized performance of SK, over a natural choice of parameterizations when the feedback is noisy.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Everything is a Race and Nakamoto Always Wins

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Free2Shard: Adaptive-adversary-resistant sharding via Dynamic Self Allocation

Propelled by the growth of large-scale blockchain deployments, much recent progress has been made in designing sharding protocols that achieve throughput scaling linearly in the number of nodes. However, existing protocols are not robust to an adversary adaptively corrupting a fixed fraction of nodes. In this paper, we propose Free2Shard -- a new architecture that achieves near-linear scaling while being secure against a fully adaptive adversary. The focal point of this architecture is a dynamic self-allocation algorithm that lets users allocate themselves to shards in response to adversarial action, without requiring a central or cryptographic proof. This architecture has several attractive features unusual for sharding protocols, including: (a) the ability to handle the regime of large number of shards (relative to the number of nodes); (b) heterogeneous shard demands; (c) requiring only a small minority to follow the self-allocation; (d) asynchronous shard rotation; (e) operation in a purely identity-free proof-of-work setting. The key technical contribution is a deep mathematical connection to the classical work of Blackwell in dynamic game theory.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

LEARN Codes: Inventing Low-latency Codes via Recurrent Neural Networks

Designing channel codes under low-latency constraints is one of the most demanding requirements in 5G standards. However, a sharp characterization of the performance of traditional codes is available only in the large block-length limit. Guided by such asymptotic analysis, code designs require large block lengths as well as latency to achieve the desired error rate. Tail-biting convolutional codes and other recent state-of-the-art short block codes, while promising reduced latency, are neither robust to channel-mismatch nor adaptive to varying channel conditions. 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 non-trivial performance. In this paper, we first propose an end-to-end learned neural code, obtained by jointly designing a Recurrent Neural Network (RNN) based encoder and decoder. This code outperforms canonical convolutional code under block settings. We then leverage this experience to propose a new class of codes under low-latency constraints, which we call Low-latency Efficient Adaptive Robust Neural (LEARN) codes. These codes outperform state-of-the-art low-latency codes and exhibit robustness and adaptivity properties. LEARN codes show the potential to design new versatile and universal codes for future communications via tools of modern deep learning coupled with communication engineering insights.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Learning in Gated Neural Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Prism Removes Consensus Bottleneck for Smart Contracts

The performance of existing permissionless smart contract platforms such as Ethereum is limited by the consensus layer. Prism is a new proof-of-work consensus protocol that provably achieves throughput and latency up to physical limits while retaining the strong guarantees of the longest chain protocol. This paper reports experimental results from implementations of two smart contract virtual machines, EVM and MoveVM, on top of Prism and demonstrates that the consensus bottleneck has been removed. Code can be found at https://github.com/wgr523/prism-smart-contracts.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Proof-of-Stake Longest Chain Protocols: Security vs Predictability

The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamoto's longest chain design achieve provable security only by allowing long-term predictability (which have serious security implications). In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto's PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols that achieve security against a 50% adversary, while only requiring short-term predictability. Our proofs present a new approach to analyzing the formal security of blockchains, based on a notion of adversary-proof convergence.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation

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 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 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 pre-computed and subtracted from the estimate. As a byproduct, we obtain a unified way of obtaining both kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Conditional Dependence via Shannon Capacity: Axioms, Estimators and Applications

We conduct an axiomatic study of the problem of estimating the strength of a known causal relationship between a pair of variables. We propose that an estimate of causal strength should be based on the conditional distribution of the effect given the cause (and not on the driving distribution of the cause), and study dependence measures on conditional distributions. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Demystifying Fixed k-Nearest Neighbor Information Estimators

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 Stögbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its $k^{\rm th}$ nearest 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 bias as a function of number of samples. We argue that the superior 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 $\ell_2$ error of the well known fixed $k$ nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Geometry of Compositionality

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Geometry of Polysemy

Vector representations of words have heralded a transformational approach to classical problems in NLP; the most popular example is word2vec. However, a single vector does not suffice to model the polysemous nature of many (frequent) words, i.e., words with multiple meanings. In this paper, we propose a three-fold approach for unsupervised polysemy modeling: (a) context representations, (b) sense induction and disambiguation and (c) lexeme (as a word and sense pair) representations. A key feature of our work is the finding that a sentence containing a target word is well represented by a low rank subspace, instead of a point in a vector space. We then show that the subspaces associated with a particular sense of the target word tend to intersect over a line (one-dimensional subspace), which we use to disambiguate senses using a clustering algorithm that harnesses the Grassmannian geometry of the representations. The disambiguation algorithm, which we call $K$-Grassmeans, leads to a procedure to label the different senses of the target word in the corpus -- yielding lexeme vector representations, all in an unsupervised manner starting from a large (Wikipedia) corpus in English. Apart from several prototypical target (word,sense) examples and a host of empirical studies to intuit and justify the various geometric representations, we validate our algorithms on standard sense induction and disambiguation datasets and present new state-of-the-art results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hiding the Rumor Source

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 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, 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, irregular and has cycles.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information Complexity Density and Simulation of Protocols

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 indepedent 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Extremal Mechanisms for Local Differential Privacy

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Spy vs. Spy: Rumor Source Obfuscation

Anonymous messaging platforms, such as Secret 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 further consider a stronger adversarial model where a subset of colluding users track the reception of messages. We show that the adaptive diffusion provides a strong protection of the anonymity of the source even under this scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Composition Theorem for Differential Privacy

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 new data processing inequalities. Our result improves over the state-of-the-art, and has immediate applications in several problems studied in the literature including differentially private multi-party computation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Deterministic Near-Optimal P2P Streaming

We consider streaming over a peer-to-peer network with homogeneous nodes in which a single source broadcasts a data stream to all the users in the system. Peers are allowed to enter or leave the system (adversarially) arbitrarily. Previous approaches for streaming in this setting have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have poor 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; our result is inspired by a recent work proposing deterministic algorithms for rumor spreading in graphs. A key innovation in our approach is in having redundant links in the distribution structure. While this leads to a reduction in the maximum streaming rate possible, we show that for the amount of redundancy used, the delay guarantee of the proposed algorithm is near optimal. We introduce a tolerance parameter that captures the worst-case transient streaming rate received by the peers during churn events and characterize the fundamental tradeoff between rate, delay and tolerance. A natural generalization of the deterministic algorithm achieves this tradeoff near optimally. Finally, the proposed deterministic algorithm is robust enough to handle various generalizations: ability to deal with heterogeneous node capacities of the peers and more complicated streaming patterns where multiple source transmissions are present.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized Response

We study the problem of interactive function computation by multiple parties possessing a single bit each in a differential privacy setting (i.e., there remains an uncertainty in any specific party's bit even when given the transcript of the interactions and all the other parties' bits). Each party is interested in computing a function, which could differ from party to party, and there could be a central observer interested in computing a separate function. Performance at each party and the central observer is measured via the accuracy of the function computed. We allow for an arbitrary cost function to measure the distortion between the true and the computed function value. Our main result is the exact optimality of a simple non-interactive protocol: each party randomizes (sufficiently) and publishes its own bit. In other words, non-interactive randomized response is exactly optimal. Each party and the central observer then separately compute their respective function to maximize the appropriate notion of their accuracy measure. The optimality 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. Finally, the optimality result is simultaneous, in terms of maximizing accuracy at each of the parties and the central observer.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Interference Channels with Half-Duplex Source Cooperation

The performance gain by allowing half-duplex source cooperation is studied for Gaussian interference channels. The source cooperation is {\em 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An asymptotically optimal push-pull method for multicasting over a random network

We consider allcast 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Interactive Interference Alignment

We study interference channels (IFC) where 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: 1) {\em In-band interaction:} sources and destinations can transmit and listen in the same channel simultaneously, enabling interaction. 2) {\em out-of-band interaction:} destinations talk back to the sources on an out-of-band channel, possible from white-space channels. 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 particular, we show the {\em first simple scheme} (having finite block length, for channels having no diversity) for $K=3,4$ that can achieve the optimal degrees of freedom of $\frac{K}{2}$ even after accounting for the cost of interaction. We also give simulation results on the finite SNR performance of interactive alignment under some settings. 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 probability 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal Noise Adding Mechanisms for Approximate Differential Privacy

We study the (nearly) optimal mechanisms in $(ε,δ)$-approximate differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. We characterize the tradeoff between $ε$ and $δ$ in utility and privacy analysis for histogram-like query functions ($\ell^1$ sensitivity), and show that the $(ε,δ)$-differential privacy is a framework not much more general than the $(ε,0)$-differential privacy and $(0,δ)$-differential privacy in the context of $\ell^1$ and $\ell^2$ cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of $\ell^1$ and $\ell^2$ cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as $(ε,δ) \to (0,0)$). We conclude that in $(ε,δ)$-differential privacy, the optimal noise magnitude and noise power are $Θ(\min(\frac{1}ε,\frac{1}δ))$ and $Θ(\min(\frac{1}{ε^2},\frac{1}{δ^2}))$, respectively, in the high privacy regime.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Optimal Mechanism 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 {\em staircase-shaped} probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a {\em 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 optimal noise probability distributions with minimum expectation of noise amplitude and power. Comparing the optimal performances with those of the Laplacian mechanism, we show that in the high privacy regime ($ε$ is small), Laplacian mechanism is asymptotically optimal as $ε\to 0$; in the low privacy regime ($ε$ is large), the minimum expectation of noise amplitude and minimum noise power are $Θ(Δe^{-\fracε{2}})$ and $Θ(Δ^2 e^{-\frac{2ε}{3}})$ as $ε\to +\infty$, while the expectation of noise amplitude and power using the Laplacian mechanism are $\fracΔε$ and $\frac{2Δ^2}{ε^2}$, where $Δ$ is the sensitivity of the query function. We conclude that the gains are more pronounced in the low privacy regime.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Optimal Mechanism in Differential Privacy: Multidimensional Setting

We derive the optimal $ε$-differentially private mechanism for a general two-dimensional real-valued (histogram-like) query function under a utility-maximization (or cost-minimization) framework for the $\ell^1$ cost function. We show that the optimal noise probability distribution has a correlated multidimensional staircase-shaped probability density function. Compared with the Laplacian mechanism, we show that in the high privacy regime (as $ε\to 0$), the Laplacian mechanism is approximately optimal; and in the low privacy regime (as $ε\to +\infty$), the optimal cost is $Θ(e^{-\fracε{3}})$, while the cost of the Laplacian mechanism is $\frac{2Δ}ε$, where $Δ$ is the sensitivity of the query function. We conclude that the gain is more pronounced in the low privacy regime. We conjecture that the optimality of the staircase mechanism holds for vector-valued (histogram-like) query functions with arbitrary dimension, and holds for many other classes of cost functions as well.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Compress-and-Forward Scheme for Relay Networks: Backword Decoding and Connection to Bisubmodular Flows

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 scheme (NNC). While it achieves the same reliable data rate as noisy network coding scheme, the backward decoding allows for a better decoding complexity as compared to 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 proved for it. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Information Capacity of an Energy Harvesting Sensor Node

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 AWGN channel using such an energy harvesting sensor node. An important part of this work involves appropriate modeling of the 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Capacity of Fading Gaussian Channel with an Energy Harvesting Sensor Node

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach

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. Our main result is the approximate optimality of a simple layering principle: {\em local physical-layer schemes combined with global routing}. We use the {\em reciprocity} of the wireless channel critically in this result. Our formal result is in the context of channel models for which "good" local schemes, that achieve the cut-set bound, exist (such as Gaussian MAC and broadcast channels, broadcast erasure networks, fast fading Gaussian networks). Layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the {\em 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 key technical idea is the modeling of a wireless network by an undirected "polymatroidal" network, for which we establish a max-flow min-cut approximation theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Information Capacity of Energy Harvesting Sensor Nodes

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Multicommodity Flows and Cuts in Polymatroidal Networks

We consider multicommodity flow and cut problems in {\em polymatroidal} networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel and Hassin in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles; 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. 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 poly-logarithmic 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 have already found aplications in wireless network information flow and we anticipate more in the future. On the technical side our key tools are the formulation and analysis of 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; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi and Lee on node-capacitated multicommodity flows and cuts. The applicability of embeddings to polymatroidal networks is of independent mathematical interest.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Approximately Optimal Wireless Broadcasting

We study a wireless broadcast network, where a single source reliably communicates independent messages to multiple destinations, with the 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 all transmit 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. The proposed scheme operates in two steps. The inner code, in which the relays perform a quantize-and-encode operation, is constructed by lifting a scheme designed for a corresponding discrete superposition network. The outer code is a Marton code for the non-Gaussian vector broadcast channel induced by the relaying scheme, and is constructed by adopting a ``receiver-centric'' viewpoint.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Interference Channels with Destination Cooperation

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 (1981) for two-user interference channels without cooperation. New upperbounds to the sum-capacity are also derived.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Interference Channels with Source Cooperation

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 (1981) 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.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Strong Consistency of the Good-Turing Estimator

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.

0 citations0 reviewsNo code linkedOpen access