In this work, we address the challenge of identifying the optimal arm in a stochastic multi-armed bandit scenario with the minimum number of arm pulls, given a predefined error probability in a fixed confidence setting. Our focus is on examining the asymptotic behavior of sample complexity and the distribution of arm weights upon termination, as the error threshold is scaled to zero, under confidence-interval based algorithms. Specifically, we analyze the asymptotic sample complexity and termination weight fractions for the well-known LUCB algorithm, and introduce a new variant, the LUCB Greedy algorithm. We demonstrate that the upper bounds on the sample complexities for both algorithms are asymptotically within a constant factor of the established lower bounds.

We study the representative arm identification (RAI) problem in the multi-armed bandits (MAB) framework, wherein we have a collection of arms, each associated with an unknown reward distribution. An underlying instance is defined by a partitioning of the arms into clusters of predefined sizes, such that for any j > i, all arms in cluster i have a larger mean reward than those in cluster j. The goal in RAI is to reliably identify a certain prespecified number of arms from each cluster while using as few arm pulls as possible. The RAI problem covers as special cases several well-studied MAB problems such as identifying the best arm or any M out of the top K, as well as both full and coarse ranking. We start by providing an instance-dependent lower bound on the sample complexity of any feasible algorithm for this setting. We then propose two algorithms, based on the idea of confidence intervals, and provide high probability upper bounds on their sample complexity, which orderwise match the lower bound. Finally, we do an empirical comparison of both algorithms along with an LUCB-type alternative on both synthetic and real-world datasets, and demonstrate the superior performance of our proposed schemes in most cases.

This work investigates the problem of best arm identification for multi-agent multi-armed bandits. We consider $N$ agents grouped into $M$ clusters, where each cluster solves a stochastic bandit problem. The mapping between agents and bandits is \textit{a priori} unknown. Each bandit is associated with $K$ arms, and the goal is to identify the best arm for each agent under a $\delta$-probably correct ($\delta$-PC) framework, while minimizing sample complexity and communication overhead. We propose two novel algorithms: \emph{Clustering then Best Arm Identification} (\texttt{Cl-BAI}) and \emph{Best Arm Identification then Clustering} (\texttt{BAI-Cl}). \texttt{Cl-BAI} employs a two-phase approach that first clusters agents based on the bandit problems they are learning, followed by identifying the best arm for each cluster. \texttt{BAI-Cl} reverses the sequence by identifying the best arms first and then clustering agents accordingly. Both algorithms exploit the successive elimination framework to ensure computational efficiency and high accuracy. Theoretical analysis establishes $\delta$-PC guarantees for both methods, derives bounds on their sample complexity, and provides a lower bound for the problem class. Moreover, when $M$ is small (a constant), we show that the sample complexity of (a variant of) \texttt{BAI-Cl} is (order-wise) minimax optimal. Experiments on synthetic and real-world (Movie Lens, Yelp) data demonstrates the superior performance of the proposed algorithms in terms of sample and communication efficiency, particularly in settings where $M \ll N$.

We study a distributed computation problem in the presence of Byzantine workers where a central node wishes to solve a task that is divided into independent sub-tasks, each of which needs to be solved correctly. The distributed computation is achieved by allocating the sub-task computation across workers with replication, as well as solving a small number of sub-tasks locally, which we wish to minimize due to it being expensive. For a general balanced job allocation, we propose a protocol that successfully solves for all sub-tasks using an optimal number of local computations under no communication constraints. Closed-form performance results are presented for cyclic allocations. Furthermore, we propose a modification to this protocol to improve communication efficiency without compromising on the amount of local computation.

We consider the problem of best arm identification in stochastic multi-armed bandits, in the setting that each arm is sampled once in each round. This uniform sampling regime is a conceptually simple setting that is relevant to many practical applications. The aim is to stop and correctly identify the best arm with probability at least 1 - 6, while keeping the number of rounds low. We derive a lower bound on the sample complexity for this setting. Thereafter, we propose two natural stopping rules for Bernoulli bandits: one based on PPR martingale confidence sequences, and the other based on the GLR statistic. Both rules are shown to match the lower bound as$fi \rightarrow 0$_ Our analysis and experiments suggest that the relative performance of the two stopping rules depends on a property of the bandit instance.

In this paper, we introduce a variation of the group testing problem where each test is specified by an ordered subset of items and returns the first defective item in the specified order or returns null if there are no defectives. The goal is to identify a small set of$K$defective items amongst a collection of size N, using as few tests as possible for perfect recovery. For the adaptive testing regime, we show that a simple scheme can find all defective items in at most$K$tests, which is optimal. For the non-adaptive setting, we first come up with a necessary and sufficient condition for any collection of tests to be feasible for recovering all the defectives. Using this, we show that any feasible non-adaptive strategy requires at least$\Omega(K^{2})$tests. In terms of achievability, it is easy to show the existence of a feasible collection of$O(K^{2}\log(N/K))$tests. We show via carefully constructed explicit designs that one can do significantly better for constant$K$. While the cases$K=1,2$are straightforward, the case$K=3$is already non-trivial and we come up with an iterative design that is asymptotically optimal and requires$\Theta(\log \log N)$, tests. Note that this is in contrast to standard binary group testing, where at least$\Omega(\log N)$tests are required. For constant$K\geq 3$, our iterative design requires only poly($\log \log N$) tests.

We study the well-known coded caching problem in an online learning framework, wherein requests arrive sequentially, and an online policy can update the cache contents based on the history of requests seen thus far. We introduce a caching policy based on the Follow-The-Perturbed-Leader principle and show that for any time horizon$\mathcal{T}$and any request sequence, it achieves a sub-linear regret of$\mathcal{O}(\sqrt{T})$with respect to an oracle that knows the request sequence beforehand. Our study marks the first examination of adversarial regret in the coded caching setup. Furthermore, we also address the issue of switching cost by establishing an upper bound on the expected number of cache updates made by our algorithm under unrestricted switching and also provide an upper bound on the regret under restricted switching when cache updates can only happen in a pre-specified subset of timeslots. Finally, we validate our theoretical insights with numerical results using a real-world dataset.

We consider the multi-access coded caching problem, which contains a central server with N files, K caches with M units of memory each and K users where each one is connected to L(≥ 1) consecutive caches, with a cyclic wrap-around. Caches are populated with content related to the files and each user then requests a file that has to be served via a broadcast message from the central server with the help of the caches. We aim to design placement and delivery policies for this setup that minimize the central servers’ transmission rate while satisfying an additional linear sub-packetization constraint. We propose policies that satisfy this constraint and derive upper bounds on the achieved server transmission rate, which upon comparison with the literature establish the improvement provided by our results. To derive our results, we map the multi-access coded caching problem to variants of the well-known index coding problem. In this process, we also derive new bounds on the optimal transmission size for a ‘structured’ index coding problem, which might be of independent interest.

We study best arm identification in a variant of the multi-armed bandit problem where the learner has limited precision in arm selection. The learner can only sample arms via certain exploration bundles, which we refer to as boxes. In particular, at each sampling epoch, the learner selects a box, which in turn causes an arm to get pulled as per a box-specific probability distribution. The pulled arm and its instantaneous reward are revealed to the learner, whose goal is to find the best arm by minimising the expected stopping time, subject to an upper bound on the error probability. We present an asymptotic lower bound on the expected stopping time, which holds as the error probability vanishes. We show that the optimal allocation suggested by the lower bound is, in general, non-unique and therefore challenging to track. We propose a modified tracking-based algorithm to handle non-unique optimal allocations, and demonstrate that it is asymptotically optimal. We also present non-asymptotic lower and upper bounds on the stopping time in the simpler setting when the arms accessible from one box do not overlap with those of others.

We study the problem of best-arm identification in a distributed variant of the multi-armed bandit setting, with a central learner and multiple agents. Each agent is associated with an arm of the bandit, generating stochastic rewards following a distribution that is a priori unknown to the learner. Further, each agent can communicate the observed rewards with the learner over a bit-constrained channel. We propose a novel quantization scheme called ICQ that can be applied to existing confidence-bound based learning algorithms such as Successive Elimination and requires only an exponentially sparse frequency of communication between the learner and the agents. We analyze the performance of ICQ applied to Successive Elimination, and show that the overall algorithm, which we call ICQ-SE, has order-optimal sample complexity and uses considerably fewer bits than existing quantization schemes to successfully identify the best arm. We are also able to verify our findings via numerical experiments.

We consider a generalization of the gradient coding framework where a dataset is divided across$n$workers and each worker transmits to a master node one or more linear combinations of the gradients over its assigned data subsets. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of straggler workers, we relax the goal to computing the sum of at least some$\alpha $fraction of the gradients. We begin by deriving a lower bound on the computation load of any scheme and also propose two strategies which achieve this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in$n$. We then propose schemes based on cyclic assignment which utilize$n$data partitions and have a lower communication load. When each worker transmits a single linear combination, we prove lower bounds on the computation load of any scheme using$n$data partitions. Finally, we describe a class of schemes which achieve different intermediate operating points for the computation and communication load and provide simulation results to demonstrate the empirical performance of our schemes.

We consider the problem of service hosting where a service provider can dynamically rent edge resources via short term contracts to ensure better quality of service to its customers. The service can also be partially hosted at the edge, in which case, customers’ requests can be partially served at the edge. The total cost incurred by the system is modeled as a combination of the rent cost, the service cost incurred due to latency in serving customers, and the fetch cost incurred as a result of the bandwidth used to fetch the code/databases of the service from the cloud servers to host the service at the edge. In this paper, we compare multiple hosting policies with regret as a metric, defined as the difference in the cost incurred by the policy and the optimal policy over some time horizon T. In particular we consider the Retro Renting (RR) and Follow The Perturbed Leader (FTPL) policies proposed in the literature and provide performance guarantees on the regret of these policies. We show that under i.i. d stochastic arrivals, RR policy has linear regret while FTPL policy has constant regret. Next, we propose a variant of FTPL, namely Wait then FTPL (W-FTPL), which also has constant regret while demonstrating much better dependence on the fetch cost. We also show that under adversarial arrivals, RR policy has linear regret while both FTPL and W-FTPL have regret O($\sqrt{T}$) which is orderoptimal.

We consider the coded caching problem with an additional privacy constraint that a user should not get any information about the demands of the other users. We first show that a demand-private scheme for$N$files and$K$users can be obtained from a non-private scheme that serves only a subset of the demands for the$N$files and$NK$users problem. We further use this fact to construct a demand-private scheme for$N$files and$K$users from a particular known non-private scheme for$N$files and$NK-K+1$users. It is then demonstrated that, the memory-rate pair$(M,\min \{N,K\}(1-M/N))$, which is achievable for non-private schemes with uncoded transmissions, is also achievable under demand privacy. We further propose a scheme that improves on these ideas by removing some redundant transmissions. The memory-rate trade-off achieved using our schemes is shown to be within a multiplicative factor of 3 from the optimal when$K < N$and of 8 when$N \leq K$. Finally, we give the exact memory-rate trade-off for demand-private coded caching problems with$N\geq K=2$.

We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures that make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this theprivate index codingproblem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where the server has the ability to multicast to any subset of users, and demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.

Coded delivery has been found to improve content delivery by reducing the data transmitted over a broadcast network. The existing works are mostly theoretical, and do not focus on building coded delivery systems for the wireless edge, especially the WiFi edge. In this paper, we first analyze the potential gains of coded delivery that employs index coding at the WiFi edge. This includes designing a system model and the algorithms therein to study the gains of coded delivery. We also compare the gains due to coding with the gains due to caching. The algorithms include segment coding algorithm at the WiFi AP and a cache replacement policy (LFU-Index) at the end user. The system model is then used as the basis to design and implement Wi-Cache, a coded delivery system at the WiFi edge. Coded delivery in Wi-Cache specifically focuses on improving HTTP based video streaming to WiFi clients. The decoding module at the end user for the coded delivery is implemented as a browser plugin that does not require device side configuration changes. We also present the effect of variable and fixed length video segment size on the perceived performance of video streaming when coded delivery is used.

We consider the problem of service hosting where an application provider can dynamically rent edge computing resources and serve user requests from the edge to deliver a better quality of service. A key novelty of this work is that we allow the service to be hosted partially at the edge which enables a fraction of the user query to be served by the edge. We model the total cost for (partially) hosting a service at the edge as a combination of the latency in serving requests, the bandwidth consumption, and the time-varying cost for renting edge resources. We propose an online policy called $\alpha -$RetroRenting $(\alpha -$RR) which dynamically determines the fraction of the service to be hosted at the edge in any time-slot, based on the history of the request arrivals and the rent cost sequence. As our main result, we derive an upper bound on $\alpha -$RR’s competitive ratio with respect to the offline optimal policy that knows the entire request arrival and rent cost sequence in advance. We conduct extensive numerical evaluations to compare the performance of $\alpha -$RR with various benchmarks for synthetic and trace-based request arrival and rent cost processes, and find several parameter regimes where $\alpha -$RR’s ability to store the service partially greatly improves cost-efficiency.

We study a variant of the canonical$k$-center problem over a set of vertices in a metric space, where the underlying distances are apriori unknown. Instead, we can query an oracle which provides noisy/incomplete estimates of the distance between any pair of vertices. We consider two oracle models: Dimension Sampling where each query to the oracle returns the distance between a pair of points in one dimension; and Noisy Distance Sampling where the oracle returns the true distance corrupted by noise. We propose active algorithms, based on ideas such as UCB and Thompson sampling developed in the closely related Multi-Armed Bandit problem, which adaptively decide which queries to send to the oracle and are able to solve the k-center problem within an approximation ratio of two with high probability. We analytically characterize instance-dependent query complexity of our algorithms and also demonstrate significant improvements over naive implementations via numerical evaluations on real-world datasets.

An Index Coding Problem (ICP) has a central server that possesses files and is connected to multiple users through a shared link. Each user demands a subset of files and possesses another subset of files as side-information. The files which are neither demanded nor possessed as side-information by a user are called its interference files. In a symmetric ICP, the relative positions of side-information and interference files are the same for all the users. In this paper, a general representation for symmetric ICPs is proposed, and using this representation, we give bounds on the optimal transmission rate for a general symmetric ICP. We identify two broad categories of symmetric ICPs: Neighboring Interference ICP (NI-ICP) and Neighboring Side-information ICP (NS-ICP). For a particular class of NI-ICP, we find the optimal transmission rate, and for another class, an order-optimal transmission rate is derived. An upper bound on the optimal transmission rate is established for NS-ICP. Furthermore, for a particular class of NS-ICP, a lower bound for the optimal transmission rate is also derived.

We consider a generalization of the recently proposed gradient coding framework where a large dataset is divided across$n$workers and each worker transmits to a master node one or more linear combinations of the gradients over the data subsets assigned to it. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of$s$straggler workers, we relax the goal of the master node to computing the sum of at least some α fraction of the gradients. The broad goal of our work is to study the optimal computation and communication load per worker for this approximate gradient coding framework. We begin by deriving a lower bound on the computation load of any feasible scheme and also propose a strategy which achieves this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in the number of workers n. We then restrict attention to schemes which utilize a number of data partitions equal to$n$and propose schemes based on cyclic assignment which have a lower communication load. When each worker transmits a single linear combination, we also prove lower bounds on the computation load of any scheme using$n$data partitions. A full version of this paper is accessible at: https://arxiv.org/abs/2102.10163

We consider the problem of identifying the subset$S$γPof elements in the support of an underlying distribution$P$whose probability value is larger than a given threshold γ, by actively querying an oracle to gain information about a sequence$X$1,$X$2, … of i.i.d. samples drawn from P. We consider two query models: (a) each query is an index$i$and the oracle return the value Xiand (b) each query is a pair of indices (i, j) and the oracle gives a binary answer confirming if Xi= Xjor not. For each of these query models, we design sequential estimation algorithms which at each round, either decide what query to send to the oracle depending on the entire history of responses, or decide to stop and output an estimate of$S$γP, which is required to be correct with some prespecified large probability. We provide upper bounds on the query complexity of the algorithms for any distribution$\mathcal{P}$and also derive lower bounds on the optimal query complexity under the two query models. We also consider noisy versions of the two query models and propose robust estimators which can effectively counter the noise in the oracle responses. A full version of this paper is accessible at: https://arxiv.org/pdf/2005.14425.pdf

The use of channel state information (CSI) at the transmitter significantly enhances the performance of wireless communication systems. However, the requirement of CSI feedback places an undue burden on the reverse link, especially in links that employ multiple-input multiple-output (MIMO) and orthogonal frequency division multiplexing (OFDM), where CSI takes the form of a precoding matrix (precoder) for each subcarrier. Typical deployments use quantization and feedback of CSI at certain subcarriers, with interpolation to fill in missing CSI at the transmitter. Past work has used the orthogonal structure of precoders with Flag manifolds for quantization and interpolation of CSI, although interpolation is complicated due to the absence of analytic expressions for geodesics on Flag manifolds. Other approaches have involved the parameterization of the precoder into scalar parameters that are amenable to quantization and interpolation. In this paper, we present efficient methods to quantize and interpolate on Flag manifolds, using both optimal algorithms as well as simplified suboptimal algorithms. Further, we unify these with the parameterization based approaches and show that these translate directly to low-complexity quantization and interpolation on Flag manifolds. Simulations reveal that the proposed precoder quantization and interpolation effectively enhance achievable rates with limited complexity.

Caching content close to the end users, e.g., at cellular base stations (BSs), WiFi access points (APs), and end user devices is known to improve efficiency and effectiveness of content delivery. This motivates the development of caching-as-a-service where edge networks and devices provide storage capacity to content providers, and enable them to strategically populate these caches to improve user experience in the targeted network. In this paper, we describe Wi-Cache, a prototype for providing caching-as-a-service at the WiFi edge. Wi-Cache is an SDN (Software Defined Networking) based distributed content caching system at the WiFi edge that uses storage at the APs for caching content. Wi-Cache caches content on wireless APs and delivers them to mobile clients when they are requested. It allows content providers to have fine-grained control over the AP-caches and also execute efficient content placement and delivery algorithms at the WiFi edge using a set of APIs that are provided by Wi-Cache. We also show the effectiveness of the Wi-Cache system using an extensive set of experiments.

We consider the problem of adaptively PAC-learning a probability distribution

We consider the demand-private coded caching problem in a noiseless broadcast network. It is known from past works that a demand-private scheme for N files and K users can be obtained from a non-private scheme for N files and NK users. We first propose a scheme that improves on this idea by removing some redundant transmissions. The memory- rate trade-off achieved using this scheme is shown to be within a multiplicative factor of 3 from the optimal for all the memory regimes when KK = 2.

Index coding and coded caching are two active research topics in information theory with strong ties to each other. Motivated by the multi-access coded caching problem, we study a new class of structured index coding problems (ICPs) which are formed by the union of several symmetric ICPs. We derive upper and lower bounds on the optimal server transmission rate for this class of ICPs and demonstrate that they differ by at most a factor of two. Finally, we apply these results to the multi-access coded caching problem to derive better bounds than the state of the art.

Motivated by the mode estimation problem of an unknown multivariate probability density function, we study the problem of identifying the point with the minimum k-th nearest neighbor distance for a given dataset of n points. We study the case where the pairwise distances are apriori unknown, but we have access to an oracle which we can query to get noisy information about the distance between any pair of points. For two natural oracle models, we design a sequential learning algorithm, based on the idea of confidence intervals, which adaptively decides which queries to send to the oracle and is able to correctly solve the problem with high probability. We derive instance-dependent upper bounds on the query complexity of our proposed scheme and also demonstrate significant improvement over the performance of other baselines via extensive numerical evaluations.

We study a multi-access variant of the popular coded caching framework, which consists of a central server with a catalog of N files, K caches with limited memory M, and K users such that each user has access to L consecutive caches with a cyclic wrap-around and requests one file from the central server's catalog. The server assists in file delivery by transmitting a message of size R over a shared error-free link and the goal is to characterize the optimal rate-memory trade-off. This setup was studied previously by Hachem et al., where an achievable rate and an information-theoretic lower bound were derived. However, the multiplicative gap between them was shown to scale linearly with the access degree L and thus order-optimality could not be established. A series of recent works have used a natural mapping of the coded caching problem to the well-known index coding problem to derive tighter characterizations of the optimal rate-memory trade-off under the additional assumption that the caches store uncoded content. We follow a similar strategy for the multi-access framework and provide new bounds for the optimal rate-memory tradeoff R*(M) over all uncoded placement policies. In particular, we derive a new achievable rate for any L ≥ 1 and a new lower bound, which works for any uncoded placement policy and L ≥ K/2. We then establish that the (multiplicative) gap between the new achievable rate and the lower bound is at most 2 independent of all parameters, thus establishing an order-optimal characterization of R*(M) for any L ≥ K/2. This is a significant improvement over the previously known gap result, albeit under the restriction of uncoded placement policies. Finally, we also characterize R*(M) exactly for a few special cases.

Content delivery networks are a key infrastructure component used by Video on Demand (VoD) services to deliver content over the Internet. We study a content delivery system consisting of a central server and multiple co-located caches, each with limited storage and service capabilities. This work evaluates the performance of such a system as a function of the storage capacity of the caches, the content replication strategy, and the service policy. This analysis can be used for a system-level optimization of these design choices. The focus of this work is on understanding the benefits of allowing caches to pool their resources to serve user requests. We show that the benefits of resource pooling depend on the popularity profile of the contents offered by the VoD service. More specifically, if the popularity does not vary drastically across contents, then resource pooling leads to an order wise reduction in central server transmission rate as the system size grows. On the other hand, if the content popularity is skewed, the central server transmission rate is of the same order with and without resource pooling.

We study a multi-access variant of the popular coded caching framework, which consists of a central server with a catalog of N files, K caches with limited memory M, and K users such that each user has access to L consecutive caches with a cyclic wrap-around and requests one file from the central server's catalog. The server assists in file delivery by transmitting a message of size R over a shared error-free link and the goal is to characterize the optimal rate-memory trade-off. This setup was proposed in [1] where an achievable rate and an information-theoretic lower bound were derived. However, the multiplicative gap between them was shown to scale linearly with the access degree L and thus order-optimality could not be established. A series of recent works have used a natural mapping of the coded caching problem to the well-known index coding problem to derive tighter characterizations of the optimal rate-memory trade-off under the additional assumption that the caches store uncoded content. We follow a similar strategy for the multi-access framework and provide new bounds for the optimal rate-memory trade-off R*(M) over all uncoded placement policies. In particular, we derive a new achievable rate for any L ≥ 1 and a new lower bound, which works for any uncoded placement policy and L ≥ K/2. We then establish that the (multiplicative) gap between the new achievable rate and the lower bound is at most 2 independent of all parameters, thus establishing an order-optimal characterization of R*(M) for any L ≥ K/2. This is in significant improvement over the gap result in [1], albeit under the restriction of uncoded placement policies. Finally, we also characterize R*(M) exactly for a few special cases.

The Jordan center of a graph is defined as a vertex whose maximum distance to other nodes in the graph is minimal, and it finds applications in facility location and source detection problems. We study properties of the Jordan center in the case of random growing trees. In particular, we consider a regular tree graph on which an infection starts from a root node and then spreads along the edges of the graph according to various random spread models. For the Independent Cascade (IC) model and the discrete Susceptible Infected (SI) model, both of which are discrete time models, we show that as the infected subgraph grows with time, the Jordan center persists on a single vertex after a finite number of timesteps.

We study the problem of index coding under the privacy requirement that receivers do not learn anything more than the messages they already have as side information and the message they want from the server. To achieve this private index coding, we consider the use of secret keys that are shared among various subsets of users and the server. We characterize key access structures that allow private index coding. For up to three receivers, we characterize the rate region of transmission and key rates and show that scalar coding is optimal; we also show that scalar linear codes are sub-optimal for four receivers. Furthermore, when no keys are available, we consider a weaker notion of privacy analogous to weak security. Finally, for a different setting in which the server is allowed to send messages exclusively to a subset of users, we study the number of transmissions required to achieve error-free decoding and privacy.

We describe the current version of Wi-Cache, a SDN framework for caching at the WiFi edge. Wi-Cache is motivated by the belief that edge caching technologies are needed to augment emerging network technologies to meet the increasing (volume, quality, and variety) demand for content, which is itself changing its characteristics significantly. Wi-Cache is being used to test new ideas for edge caching. Specifically, Wi-Cache is a framework for edge caching which allows caching and delivery of content on WiFi APs. Apart from a network induced handoff of clients, it allows communication between the APs for content delivery. We have also developed an API that is exposed for implementation of algorithms for content delivery and placement, and cache replacement.

In this work, we focus on distributed cache systems with non-uniform storage capacity across caches. We compare the performance of our system with the performance of a system with the same cumulative storage distributed evenly across the caches. We characterize the extent to which the performance of the distributed cache system deteriorates due to storage heterogeneity. The key takeaway from this work is that the effects of heterogeneity in the storage capabilities depend heavily on the popularity profile of the contents being cached and delivered. We analytically show that compared to the case where contents popularity is comparable across contents, lopsided popularity profiles are more tolerant to heterogeneity in storage capabilities. We validate our theoretical results via simulations.

We study the caching problem when we are allowed to match each user to one of a subset of caches after its request is revealed. We focus on non-uniformly popular content, specifically when the file popularities obey a Zipf distribution. We study two extremal schemes: one focusing on coded server transmissions while ignoring matching capabilities and the other focusing on adaptive matching while ignoring potential coding opportunities. We derive the rates achieved by these schemes and characterize the regimes in which one outperforms the other. We also compare them to information-theoretic outer bounds and finally propose a hybrid scheme that generalizes ideas from the two schemes and performs at least as well as either of them in most memory regimes.

Recent work by Maddah-Ali and Niesen (2014) introduced coded caching which demonstrated the benefits of joint design of storage and transmission policies in content delivery networks. They studied a setup where a server communicates with a set of users, each equipped with a local cache, over a shared error-free link and proposed an order-optimal caching and delivery scheme. In this paper, we introduce the problem of private coded caching where we impose the additional constraint that no user learns any information about the contents of the files it did not request from what is stored in its cache and the server transmissions. We propose a feasible scheme for this setting and demonstrate its order-optimality by deriving information-theoretic lower bounds.

We study the coded caching problem when we are allowed to match users to caches based on their requested files. We focus on the case where caches are divided into clusters and each user can be assigned to a unique cache from a specific cluster. We show that neither the coded delivery strategy (approximately optimal when the user-cache assignment is pre-fixed) nor the uncoded replication strategy (approximately optimal when all caches belong to a single cluster) is sufficient for all memory regimes. We propose a hybrid solution that combines ideas from both schemes and that performs at least as well as either strategy in most memory regimes. Finally, we show that this hybrid strategy is approximately optimal in most memory regimes.

We study the caching problem when we are allowed to match each user to one of a subset of caches after its request is revealed. We focus on non-uniformly popular content, specifically when the file popularities obey a Zipf distribution. We study two extremal schemes, one focusing on coded server transmissions while ignoring matching capabilities, and the other focusing on adaptive matching while ignoring potential coding opportunities. We derive the rates achieved by these schemes and characterize the regimes in which one outperforms the other. We also compare them to information-theoretic outer bounds, and finally propose for certain cases a hybrid scheme that generalizes ideas from the two schemes and performs at least as well as either of them in most memory regimes.

To address the exponentially rising demand for wireless content, the use of caching is emerging as a potential solution. It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. Coded caching is well suited to emerging heterogeneous wireless architectures which consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). This enables design of coded caching-and-delivery schemes that equip APs with storage, and place content in them in a way that creates coded-multicast opportunities for combining with macro-cell broadcast to satisfy users even with different demands. Such coded-caching schemes have been shown to be order-optimal with respect to the BS transmission rate, for a system with single-level content, i.e., one where all content is uniformly popular. In this paper, we consider a system with non-uniform popularity content which is divided into multiple levels, based on varying degrees of popularity. The main contribution of this paper is the derivation of an order-optimal scheme which judiciously shares cache memory among files with different popularities. To show order-optimality we derive new information-theoretic lower bounds, which use a sliding-window entropy inequality, effectively creating a non-cut-set bound. We also extend the ideas to when users can access multiple caches along with the broadcast. Finally, we consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup), and demonstrate a dichotomy in the order-optimal strategies for these two extreme cases.

Motivated by the ability of modern terminals to receive simultaneously from multiple networks (e.g., WLAN and Cellular), we extend the single shared link network with caching at the user nodes to the case of r parallel partially shared links, where users in different classes receive from the server simultaneously and in parallel through different set of links. For this setting, we give an order-optimal rate and (maximal) delay region characterization for the case of r = 2 links with two classes of users, one receiving only from link 1 and the other from both links 1 and 2. We also extend these results to r = 3 with three classes of users, receiving from link 1, from links 1 and 2, and from links 1 and 3, respectively.

Recent work by Maddah-Ali and Niesen introduced coded caching which demonstrated the benefits of joint design of storage and transmission policies in content delivery networks. They studied a setup where a server communicates with a set of users, each equipped with a local cache, over a shared error-free link and proposed an order-optimal caching and delivery scheme. In this paper, we introduce the problem of secretive coded caching where we impose the additional constraint that a user should not be able to learn anything, from either the content stored in its cache or the server transmissions, about a file it did not request. We propose a feasible scheme for this setting and demonstrate its order-optimality with respect to information-theoretic lower bounds.

We revisit the problem of inferring the overall ranking among entities in the framework of Bradley-Terry-Luce (BTL) model, based on available empirical data on pairwise preferences. By a simple transformation, we can cast the problem as that of solving a noisy linear system, for which a ready algorithm is available in the form of the randomized Kaczmarz method. This scheme is provably convergent and has excellent empirical performance. Convergence, convergence rate, and error analysis of the proposed algorithm are presented and several numerical experiments are conducted whose results validate our theoretical findings.

Caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to locally deliver the part of the content, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider, in this paper, a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both the layers can simultaneously operate at approximately the minimum rate.

Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.

It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. This has also been extended to the case when content has non-uniform popularity through several models. In this paper we focus on a multi-level popularity model, where content is divided into levels based on popularity. We consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup). When the capacity approximation is universal (independent of number of popularity levels as well as number of users, files and caches), we demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the levels is order-optimal, whereas for the single-user case clustering popularity levels and allocating all the memory to them is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.

Motivated by the need to secure cyber-physical systems against attacks, we consider the problem of estimating the state of a noisy linear dynamical system when a subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm and derive (optimal) bounds on the achievable state estimation error. In addition, as a result of independent interest, we give a coding theoretic interpretation for prior work on secure state estimation against sensor attacks in a noiseless dynamical system.

Recent work has demonstrated that, for content caching, joint design of storage and delivery can yield significant benefits over conventional caching approaches. This is based on storing content in the caches in a way that creates coded-multicast opportunities even among users with different demands. Such a coded-caching scheme has been shown to be order-optimal for a caching system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with content divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an information-theoretic outer bound for the multi-level setup, and the demonstration that, under some natural regularity conditions, a memory-sharing scheme, which operates each level in isolation according to a single-level coded caching scheme, is in fact order-optimal with respect to this outer bound.

It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.

The performance of cooperation strategies for broadcast services sharing a common wireless channel is studied in the framework of coalitional game theory. Two strategies are examined. The first represents an open sharing model where each service provider is allowed to transmit at any time but simultaneous transmissions result in interference. It is shown analytically that in the absence of coordination cost, the grand coalition formed by all providers cooperating to avoid simultaneous transmissions is both sum-rate optimal and stable. The second strategy represents an orthogonal access method where service providers are granted exclusive access to a subset of the available channels, each having a guaranteed successful transmission opportunity. In the absence of coordination cost, the grand coalition where all providers cooperate by sharing their guaranteed right to access the channel is sum-rate optimal but unstable, in the sense that some group of providers may have an incentive to deviate from the grand coalition. In the presence of coordination cost, a different scenario arises. In both models large coalitions do not form, and simulation results suggest that the open access model for large networks can lead to a regime where performance is considerably limited by interference.

Consider a network where an unidentified source starts a rumor. The rumor spreads along the edges of the network to other nodes in the network. After a sufficiently long amount of time, we observe a subset of the nodes that have heard the rumor, and using this information wish to identify the source. Optimal estimators were recently proposed for regular (exponential growth) and irregular geometric (polynomial growth) trees when all nodes that heard the rumor reveal themselves. We provide the extension to the case in which nodes reveal whether they have heard the rumor with probability p, independent of each other. For geometric trees and p > 0, we achieve the same performance as the optimal estimator with p = 1. For regular trees, the estimator can achieve performance within ε of the optimal, provided that p is larger than a threshold.

We consider the problem of distributed computation of a target function over a two-user deterministic multiple-access channel. If the target and channel functions are matched (i.e., compute the same function), significant performance gains can be obtained by jointly designing the communication and computation tasks. However, in most situations there is mismatch between these two functions. In this work, we analyze the impact of this mismatch on the performance gains achievable with joint communication and computation designs over separation-based designs. We show that for most pairs of target and channel functions there is no such gain, and separation of communication and computation is optimal.

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, semi-injective, and linear target functions over finite fields. Computing capacity bounds and achievability are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, injective, and semi-injective target functions. Computing capacity bounds are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

This paper considers the following network computation problem: n nodes are placed on a √n×√n grid, each node is connected to every other node within distance r(n) from itself, and is given an arbitrary input bit. Nodes communicate with each other so that finally a designated sink node can compute a target function f of the input bits. We focus on computing the identity function and the class of symmetric functions under two different communication models. We first consider a noiseless model where links are independent and noise-free, suitable for modeling wired networks. Next, we study a noisy broadcast model in which when a node transmits a bit, each of its neighbors receives a noisy copy of the bit. This is a simple model for wireless communications, originally proposed by El Gamal (1987). We use the protocol model for interference and nodes which do not share neighbors are allowed to transmit simultaneously. For every connection radius r(n), we present lower bounds on the minimum number of transmissions and the minimum number of time slots required to compute f. We then describe efficient protocols which can match both these lower bounds up to a constant factor.

The following network computing problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target functionfof the messages. The objective is to maximize the average number of timesfcan be computed per network usage, i.e., the “computing capacity”. The network coding problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network min-cut upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks. It is also tight for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.

This paper considers the following network computation problem:nnodes are placed on a √n × √n grid, each node is connected to every other node within distancer(n) of itself, and it is assigned an arbitrary input bit. Nodes communicate with their neighbors and a designated sink node computes a functionfof the input bits, wherefis either the identity or a symmetric function. We first consider a model where links are interference and noise-free, suitable for modeling wired networks. Then, we consider a model suitable for wireless networks. Due to interference, only nodes which do not share neighbors are allowed to transmit simultaneously, and when a node transmits a bit, all of its neighbors receive an independent noisy copy of the bit. We present lower bounds on the minimum number of transmissions and on the minimum number of time slots required to computef. We also describe efficient schemes that match both of these lower bounds up to a constant factor and are thus jointly (near) optimal with respect to the number of transmissions and the number of time slots required for computation. At the end of the paper, we extend results on symmetric functions to general network topologies, and obtain a corollary that answers an open question posed by El Gamal in 1987 regarding the computation of the parity function over ring and tree networks.

This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.

We study the computation of the arithmetic sum of the q-ary source messages in the reverse butterfly network. Specifically, we characterize the maximum rate at which the message sum can be computed at the receiver and demonstrate that linear coding is suboptimal.

This paper considers the following network computation problem: n nodes are placed on a radic(n)timesradic(n) grid, each node in the network is connected to every other node within distance r(n) of itself, and is given an arbitrary input bit. Connected nodes communicate with each other over independent binary symmetric channels of a given transition probability epsiv ges 0, and an arbitrarily designated node computes a symmetric target function f of the input bits. We characterize up to order the minimum number of transmissions required to compute f with a probability of error less than any given positive constant delta. As a side result, we answer an open question posed by El Gamal in 1987 regarding the number of transmissions required to compute the parity function over ring and tree networks.

The throughput of delay sensitive traffic in a Rayleigh fading network is studied by adopting a scaling limit approach. The case of study is that of a pair of nodes establishing a data stream that has routing priority over all the remaining traffic in the network. For every delay constraint, upper and lower bounds on the achievable information rate between the two end-points of the stream are obtained as the network size grows. The analysis concerns decentralized schemes, in the sense that all nodes make next-hop decisions based only on local information, namely their channel strength to other nodes in the network and the position of the destination node. This is particularly important in a fading scenario, where the channel strength varies with time and hence pre-computing routes can be of little help. Natural applications are remote surveillance using sensor networks, and communication in emergency scenarios.

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

We consider the clustering properties of one-dimensional sensor networks where the nodes are randomly deployed. Unlike most other work on randomly deployed networks, ours assumes that the node locations are drawn from a non uniform distribution. Specifically, we consider an exponential distribution. We first obtain the probability that there exists a path between two labeled nodes in a randomly deployed network and obtain the limiting behavior of this probability. The probability mass function (pmf) for the number of components in the network is then obtained. We show that the number of components in the network converges in distribution. We also derive the probabilities for different locations of the components. We then obtain the probability for the existence of a k-sized component and components of size /spl ges/k. Asymptotics in the number of nodes in the network are computed for these probabilities. An interesting result is that, as the number of nodes, n, in the network tends to infinity, a giant component, in which a specific fraction, /spl alpha/, of the nodes form a component, almost surely does not exist for any 0n/sub 0/, the network almost surely does not have a giant component.