  This paper presents new solutions for Private Information Retrieval (PIR)
with side information. This problem is motivated by PIR settings in which a
client has side information about the data held by the servers and would like
to leverage this information in order to improve the download rate. The problem
of PIR with side information has been the subject of several recent studies
that presented achievability schemes as well as converses for both multi-server
and single-server settings. However, the solutions for the multi-server
settings adapted from the solutions for the single-server setting in a rather
straightforward manner, relying on the concept of super-messages. Such
solutions require an exponential degree of sub-packetization (in terms of the
number of messages).
  This paper makes the following contributions. First, we revisit the PIR
problem with side information and present a new approach to leverage side
information in the context of PIR. The key idea of our approach is a randomized
algorithm to determine the linear combinations of the sub-packets that need to
be recovered from each server. In addition, our approach takes advantage of the
fact that the identity of the side information messages does not need to be
kept private, and, as a result, the information retrieval scheme does not need
to be symmetric. Second, we present schemes for PIR with side information that
achieve a higher rate than previously proposed solutions and require a
significantly lower degree of sub-packetization (linear in the number of
servers). Our scheme not only achieves the highest known download rate for the
problem at hand but also invalidates a previously claimed converse bound on the
maximum achievable download rate.
