  We consider a multi-user variant of the private information retrieval problem
described as follows. Suppose there are $D$ users, each of which wants to
privately retrieve a distinct message from a server with the help of a trusted
agent. We assume that the agent has a random subset of $M$ messages that is not
known to the server. The goal of the agent is to collectively retrieve the
users' requests from the server. For protecting the privacy of users, we
introduce the notion of individual-privacy -- the agent is required to protect
the privacy only for each individual user (but may leak some correlations among
user requests). We refer to this problem as Individually-Private Information
Retrieval with Side Information (IPIR-SI).
  We first establish a lower bound on the capacity, which is defined as the
maximum achievable download rate, of the IPIR-SI problem by presenting a novel
achievability protocol. Next, we characterize the capacity of IPIR-SI problem
for $M = 1$ and $D = 2$. In the process of characterizing the capacity for
arbitrary $M$ and $D$ we present a novel combinatorial conjecture, that may be
of independent interest.
