BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Nikhil Karamchandani

Nikhil Karamchandani contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITNetworking and Internet ArchitectureData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingMachine Learningeess.SYInformation Retrievalmath.COSocial and Information NetworksSystems and Control

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
13works
0followers
11topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

13 published item(s)

preprint2024arXiv

On Distributed Multi-User Secret Sharing with Multiple Secrets per User

We consider a distributed multi-user secret sharing (DMUSS) setting in which there is a dealer, $n$ storage nodes, and $m$ secrets. Each user demands a $t$-subset of $m$ secrets. Earlier work in this setting dealt with the case of $t=1$; in this work, we consider general $t$. The user downloads shares from the storage nodes based on the designed access structure and reconstructs its secrets. We identify a necessary condition on the access structures to ensure weak secrecy. We also make a connection between access structures for this problem and $t$-disjunct matrices. We apply various $t$-disjunct matrix constructions in this setting and compare their performance in terms of the number of storage nodes and communication complexity. We also derive bounds on the optimal communication complexity of a distributed secret sharing protocol. Finally, we characterize the capacity region of the DMUSS problem when the access structure is specified.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Greedy k-Center from Noisy Distance Samples

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, Thompson Sampling and Track-and-Stop 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 two real-world datasets (Tiny ImageNet and UT Zappos50K).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Gradient Coding with Partial Recovery

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 $α$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Online Partial Service Hosting at the Edge

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 $α$-RetroRenting ($α$-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 $α$-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 $α$-RR with various benchmarks for synthetic and trace-based request arrival and rent cost processes, and find several parameter regimes where $α$-RR's ability to store the service partially greatly improves cost-efficiency.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Fundamental Limits of Demand-Private Coded Caching

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

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Maintaining Ferment: On Opinion Control Over Social Networks

We consider the design of external inputs to achieve a control objective on the opinions, represented by scalars, in a social network. The opinion dynamics follow a variant of the discrete-time Friedkin-Johnsen model. We first consider two minimum cost optimal control problems over a finite interval $(T_0,T),$ $T_0 >0$ -- (1) TF where opinions at all nodes should exceed a given $τ,$ and (2) GF where a scalar function of the opinion vector should exceed a given $τ.$ For both problems we first provide a Pontryagin maximum principle (PMP) based control function when the controllable nodes are specified. We then show that both these problems exhibit the turnpike property where both the control function and the state vectors stay near their equilibrium for a large fraction of the time. This property is then used to choose the optimum set of controllable nodes. We then consider a third system, MF, which is a cost-constrained optimal control problem where we maximize the minimum value of a scalar function of the opinion vector over $(T_0,T).$ We provide a numerical algorithm to derive the control function for this problem using non-smooth PMP based techniques. Extensive numerical studies illustrate the three models, control techniques and corresponding outcomes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Query complexity of heavy hitter estimation

We consider the problem of identifying the subset $\mathcal{S}^γ_{\mathcal{P}}$ of elements in the support of an underlying distribution $\mathcal{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, \ldots$ of $i.i.d.$ samples drawn from $\mathcal{P}$. We consider two query models: $(a)$ each query is an index $i$ and the oracle return the value $X_i$ and $(b)$ each query is a pair $(i,j)$ and the oracle gives a binary answer confirming if $X_i = X_j$ or 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 $\mathcal{S}^γ_{\mathcal{P}}$, which is required to be correct with some pre-specified 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Index Coding at the WiFi Edge: An Implementation Study for Video Delivery

HTTP based video streaming has become the de facto standard for video content delivery across different video streaming services. However, video content delivery continues to be challenged at the wireless edge by inadequate and highly variable bandwidth. In this paper, we describe WiCode, a platform that improves HTTP based video content delivery at the WiFi edge. WiCode uses coded delivery at the WiFi AP to reduce data transmissions in order to improve the perceived performance of video streaming at the users. WiCode performs index coding on video segments to reduce the number of bits transmitted. Further, it also performs index coding on UDP packets that are retransmitted to reduce the number of bits transmitted. This paper describes the design and implementation of WiCode, and the practical gains achievable due to employing coded delivery in a real system taking into account the overheads introduced by WiCode. The WiCode module at the client side is a browser plugin that does not require any client side device configuration changes. We also show the effect of variable and fixed length segment size on the perceived performance of WiCode.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Online Caching and Coding at the WiFi Edge: Gains and Tradeoffs

Video content delivery at the wireless edge continues to be challenged by insufficient bandwidth and highly dynamic user behavior which affects both effective throughput and latency. Caching at the network edge and coded transmissions have been found to improve user performance of video content delivery. The cache at the wireless edge stations (BSs, APs) and at the users&#39; end devices can be populated by pre-caching content or by using online caching policies. In this paper, we propose a system where content is cached at the user of a WiFi network via online caching policies, and coded delivery is employed by the WiFi AP to deliver the requested content to the user population. The content of the cache at the user serves as side information for index coding. We also propose the LFU-Index cache replacement policy at the user that demonstrably improves index coding opportunities at the WiFi AP for the proposed system. Through an extensive simulation study, we determine the gains achieved by caching and index by coding. Next, we analyze the tradeoffs between them in terms of data transmitted, latency, and throughput for different content request behaviors from the users. We also show that the proposed cache replacement policy performs better than traditional cache replacement policies like LRU and LFU.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Private Index Coding

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 which 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 the private index coding problem. 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 no keys are shared among the users and provide some necessary and sufficient conditions for feasibility in this setting under a weaker notion of privacy. If the server has the ability to multicast to any subset of users, we demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rate-Memory Trade-off for Multi-access Coded Caching with Uncoded Placement

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&#39;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 trade-off $R^*(M)$ over all uncoded placement policies. In particular, we derive a new achievable rate for any $L \ge 1$ and a new lower bound, which works for any uncoded placement policy and $L \ge 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\ge 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Resource Pooling in Large-Scale Content Delivery Systems

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, resource pooling can lead to significant improvements in the system performance. In contrast, if the content popularity is uneven, the benefits of resource pooling are negligible.

0 citations0 reviewsNo code linkedOpen access