Tootfinder

The Capacity of Semantic Private Information Retrieval with Colluding Servers
Mohamed Nomeir, Alptug Aytekin, Sennur Ulukus
https://arxiv.org/abs/2507.15818

The Capacity of Semantic Private Information Retrieval with Colluding Servers
We study the problem of semantic private information retrieval (Sem-PIR) with $T$ colluding servers (Sem-TPIR), i.e., servers that collectively share user queries. In Sem-TPIR, the message sizes are different, and message retrieval probabilities by any user are not uniform. This is a generalization of the classical PIR problem where the message sizes are equal and message retrieval probabilities are identical. The earlier work on Sem-PIR considered the case of no collusions, i.e., the collusion…

Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems
Shreya Meel, Sennur Ulukus
https://arxiv.org/abs/2507.17736 https://arxiv.…

Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems
We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we estab…