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

Alex Sprintson

Alex Sprintson contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITInformation Retrievaleess.SPmath.CONetworking and Internet Architecture

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
6topics
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

12 published item(s)

preprint2022arXiv

Group Testing on General Set-Systems

Group testing is one of the fundamental problems in coding theory and combinatorics in which one is to identify a subset of contaminated items from a given ground set. There has been renewed interest in group testing recently due to its applications in diagnostic virology, including pool testing for the novel coronavirus. The majority of existing works on group testing focus on the \emph{uniform} setting in which any subset of size $d$ from a ground set $V$ of size $n$ is potentially contaminated. In this work, we consider a {\em generalized} version of group testing with an arbitrary set-system of potentially contaminated sets. The generalized problem is characterized by a hypergraph $H=(V,E)$, where $V$ represents the ground set and edges $e\in E$ represent potentially contaminated sets. The problem of generalized group testing is motivated by practical settings in which not all subsets of a given size $d$ may be potentially contaminated, rather, due to social dynamics, geographical limitations, or other considerations, there exist subsets that can be readily ruled out. For example, in the context of pool testing, the edge set $E$ may consist of families, work teams, or students in a classroom, i.e., subsets likely to be mutually contaminated. The goal in studying the generalized setting is to leverage the additional knowledge characterized by $H=(V,E)$ to significantly reduce the number of required tests. The paper considers both adaptive and non-adaptive group testing and makes the following contributions. First, for the non-adaptive setting, we show that finding an optimal solution for the generalized version of group testing is NP-hard. For this setting, we present a solution that requires $O(d\log{|E|})$ tests, where $d$ is the maximum size of a set $e \in E$. Our solutions generalize those given for the traditional setting and are shown to be of order-optimal size $O(\log{|E|})$ for hypergraphs with edges that have ``large'' symmetric differences. For the adaptive setting, when edges in $E$ are of size exactly $d$, we present a solution of size $O(\log{|E|}+d\log^2{d})$ that comes close to the lower bound of $Ω(\log{|E|} + d)$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-Message Private Information Retrieval: A Scalar Linear Solution

In recent years, the Multi-message Private Information Retrieval (MPIR) problem has received significant attention from the research community. In this problem, a user wants to privately retrieve $D$ messages out of $K$ messages whose identical copies are stored on $N$ remote servers, while maximizing the download rate. The MPIR schemes can find applications in many practical scenarios and can serve as an important building block for private computation and private machine learning applications. The existing solutions for MPIR require a large degree of subpacketization, which can result in large overheads, high complexity, and impose constraints on the system parameters. These factors can limit practical applications of the existing solutions. In this paper, we present a methodology for the design of scalar-linear MPIR schemes. Such schemes are easy to implement in practical systems as they do not require partitioning of messages into smaller size sub-messages and do not impose any constraints on the minimum required size of the messages. Focusing on the case of $N=D+1$, we show that when $D$ divides $K$, our scheme achieves the capacity, where the capacity is defined as the maximum achievable download rate. When the divisibility condition does not hold, the performance of our scheme is the same or within a small additive margin compared to the best known scheme that requires a high degree of subpacketization.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Noisy Group Testing with Side Information

Group testing has recently attracted significant attention from the research community due to its applications in diagnostic virology. An instance of the group testing problem includes a ground set of individuals which includes a small subset of infected individuals. The group testing procedure consists of a number of tests, such that each test indicates whether or not a given subset of individuals includes one or more infected individuals. The goal of the group testing procedure is to identify the subset of infected individuals with the minimum number of tests. Motivated by practical scenarios, such as testing for viral diseases, this paper focuses on the following group testing settings: (i) the group testing procedure is noisy, i.e., the outcome of the group testing procedure can be flipped with a certain probability; (ii) there is a certain amount of side information on the distribution of the infected individuals available to the group testing algorithm. The paper makes the following contributions. First, we propose a probabilistic model, referred to as an interaction model, that captures the side information about the probability distribution of the infected individuals. Next, we present a decoding scheme, based on the belief propagation, that leverages the interaction model to improve the decoding accuracy. Our results indicate that the proposed algorithm achieves higher success probability and lower false-negative and false-positive rates when compared to the traditional belief propagation especially in the high noise regime.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Linear Capacity of Single-Server Individually-Private Information Retrieval with Side Information

This paper considers the problem of single-server Individually-Private Information Retrieval with side information (IPIR). In this problem, there is a remote server that stores a dataset of $K$ messages, and there is a user that initially knows $M$ of these messages, and wants to retrieve $D$ other messages belonging to the dataset. The goal of the user is to retrieve the $D$ desired messages by downloading the minimum amount of information from the server while revealing no information about whether an individual message is one of the $D$ desired messages. In this work, we focus on linear IPIR schemes, i.e., the IPIR schemes in which the user downloads only linear combinations of the original messages from the server. We prove a converse bound on the download rate of any linear IPIR scheme for all $K,D,M$, and show the achievability of this bound for all $K,D,M$ satisfying a certain divisibility condition. Our results characterize the linear capacity of IPIR, which is defined as the maximum achievable download rate over all linear IPIR schemes, for a wide range of values of $K,D,M$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Role of Reusable and Single-Use Side Information in Private Information Retrieval

This paper introduces the problem of Private Information Retrieval with Reusable and Single-use Side Information (PIR-RSSI). In this problem, one or more remote servers store identical copies of a set of $K$ messages, and there is a user that initially knows $M$ of these messages, and wants to privately retrieve one other message from the set of $K$ messages. The objective is to design a retrieval scheme in which the user downloads the minimum amount of information from the server(s) while the identity of the message wanted by the user and the identities of an $M_1$-subset of the $M$ messages known by the user (referred to as reusable side information) are protected, but the identities of the remaining $M_2=M-M_1$ messages known by the user (referred to as single-use side information) do not need to be protected. The PIR-RSSI problem reduces to the classical Private Information Retrieval (PIR) problem when ${M_1=M_2=0}$, and reduces to the problem of PIR with Private Side Information or PIR with Side Information when ${M_1\geq 1,M_2=0}$ or ${M_1=0,M_2\geq 1}$, respectively. In this work, we focus on the single-server setting of the PIR-RSSI problem. We characterize the capacity of this setting for the cases of ${M_1=1,M_2\geq 1}$ and ${M_1\geq 1,M_2=1}$, where the capacity is defined as the maximum achievable download rate over all PIR-RSSI schemes. Our results show that for sufficiently small values of $K$, the single-use side information messages can help in reducing the download cost only if they are kept private; and for larger values of $K$, the reusable side information messages cannot help in reducing the download cost.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Minimizing the alphabet size in codes with restricted error sets

This paper focuses on error-correcting codes that can handle a predefined set of specific error patterns. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size for this generalized setting and the combinatorial properties of a hypergraph that represents the prespecified collection of error patterns. We also show a connection between error and erasure correcting codes in this specialized setting. This allows us to establish bounds on the minimum alphabet size and show an advantage of non-linear codes over linear codes in a generalized setting. We also consider a variation of the problem which allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Private Linear Transformation: The Individual Privacy Case

This paper considers the single-server Private Linear Transformation (PLT) problem when individual privacy is required. In this problem, there is a user that wishes to obtain $L$ linear combinations of a $D$-subset of messages belonging to a dataset of $K$ messages stored on a single server. The goal is to minimize the download cost while keeping the identity of every message required for the computation individually private. The individual privacy requirement implies that, from the perspective of the server, every message is equally likely to belong to the $D$-subset of messages that constitute the support set of the required linear combinations. We focus on the setting in which the matrix of coefficients pertaining to the required linear combinations is the generator matrix of a Maximum Distance Separable code. We establish lower and upper bounds on the capacity of PLT with individual privacy, where the capacity is defined as the supremum of all achievable download rates. We show that our bounds are tight under certain divisibility conditions. In addition, we present lower bounds on the capacity of the settings in which the user has a prior side information about a subset of messages.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Private Linear Transformation: The Joint Privacy Case

We introduce the problem of Private Linear Transformation (PLT). This problem includes a single (or multiple) remote server(s) storing (identical copies of) $K$ messages and a user who wants to compute $L$ linear combinations of a $D$-subset of these messages by downloading the minimum amount of information from the server(s) while protecting the privacy of the entire set of $D$ messages. This problem generalizes the Private Information Retrieval and Private Linear Computation problems. In this work, we focus on the single-server case. For the setting in which the coefficient matrix of the required $L$ linear combinations generates a Maximum Distance Separable (MDS) code, we characterize the capacity -- defined as the supremum of all achievable download rates, for all parameters $K, D, L$. In addition, we present lower and/or upper bounds on the capacity for the settings with non-MDS coefficient matrices and the settings with a prior side information.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Combinatorial View of the Service Rates of Codes Problem, its Equivalence to Fractional Matching and its Connection with Batch Codes

We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation, as we show, is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Joint Index Coding and Incentive Design for Selfish Clients

The index coding problem includes a server, a group of clients, and a set of data chunks. While each client wants a subset of the data chunks and already has another subset as its side information, the server transmits some uncoded data chunks or coded data chunks to the clients over a noiseless broadcast channel. The objective of the problem is to satisfy the demands of all clients with the minimum number of transmissions. In this paper, we investigate the index coding setting from a game-theoretical perspective. We consider selfish clients, where each selfish client has private side information and a private valuation of each data chunk it wants. In this context, our objectives are following: 1) to motivate each selfish client to reveal the correct side information and true valuation of each data chunk it wants; 2) to maximize the social welfare, i.e., the total valuation of the data chunks recovered by the clients minus the total cost incurred by the transmissions from the server. Our main contribution is to jointly develop coding schemes and incentive schemes for achieving the first objective perfectly and achieving the second objective optimally or approximately with guaranteed approximation ratios (potentially within some restricted sets of coding matrices).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Minimizing the alphabet size of erasure codes with restricted decoding sets

A Maximum Distance Separable code over an alphabet $F$ is defined via an encoding function $C:F^k \rightarrow F^n$ that allows to retrieve a message $m \in F^k$ from the codeword $C(m)$ even after erasing any $n-k$ of its symbols. The minimum possible alphabet size of general (non-linear) MDS codes for given parameters $n$ and $k$ is unknown and forms one of the central open problems in coding theory. The paper initiates the study of the alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified subset of all possible erasure patterns, naturally represented by an $n$-vertex $k$-uniform hypergraph. We relate the minimum possible alphabet size of such codes to the strong chromatic number of the hypergraph and analyze the tightness of the obtained bounds for both the linear and non-linear settings. We further consider variations of the problem which allow a small probability of decoding error.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Private Computation with Individual and Joint Privacy

This paper considers the problem of single-server Private Computation (PC) in the presence of Side Information (SI). In this problem, there is a server that stores $K$ i.i.d. messages, and a user who has a subset of $M$ uncoded messages or a coded linear combination of them as side information, where the identities of these messages are unknown to the server. The user wants to privately compute (via downloading information from the server) a linear combination of a subset of $D$ other messages, where the identities of these messages must be kept private individually or jointly. For each setting, we define the capacity as the supremum of all achievable download rates. We characterize the capacity of both PC with coded and uncoded SI when individual privacy is required, for all $K, M, D$. Our results indicate that both settings have the same capacity. In addition, we establish a non-trivial lower bound on the capacity of PC with coded SI when joint privacy is required, for a range of parameters $K, M, D$. This lower bound is the same as the lower bound we previously established on the capacity of PC with uncoded SI when joint privacy is required.

0 citations0 reviewsNo code linkedOpen access