2021/07/02 by Giulietti, Massimo, Sabatini, Arianna, Timpanella, Marco · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2107.01169
A k-server Private Information Retrieval (PIR) code is a binary linear [m,s]-code admitting a generator matrix such that for every integer i with 1≤ i≤ s there exist k disjoint subsets of columns (called recovery sets) that add up to the vector of weight one, with the single 1 in position i. As shown in \citeFazeli1, a k-server PIR code is useful to reduce the storage overhead of a traditional k-server PIR protocol. Finding k-server PIR codes with a small blocklength for a given dimension has recently become an important research challenge. In this work, we propose new constructions of PIR codes from combinatorial structures, introducing the notion of k-partial packing. Several bounds over the existing literature are improved.