惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Engineering at Meta
Engineering at Meta
J
Java Code Geeks
I
InfoQ
腾讯CDC
Vercel News
Vercel News
IT之家
IT之家
V
Visual Studio Blog
P
Proofpoint News Feed
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
G
Google Developers Blog
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
博客园 - 叶小钗
有赞技术团队
有赞技术团队
月光博客
月光博客
Martin Fowler
Martin Fowler
量子位
L
LangChain Blog
B
Blog
Last Week in AI
Last Week in AI
博客园 - 司徒正美
Microsoft Security Blog
Microsoft Security Blog
博客园 - 聂微东
Microsoft Azure Blog
Microsoft Azure Blog
A
About on SuperTechFans

cs.IT updates on arXiv.org

Theoretical Limits of Language Model Alignment $f$-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analyses A Unified Measure-Theoretic View of Diffusion, Score-Based, and Flow Matching Generative Models When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation When Semantic Communication Meets Queueing: Cross-Layer Latency and Task Fidelity Optimization Convexity in Disguise: A Theoretical Framework for Nonconvex Low-Rank Matrix Estimation Conditional Diffusion Under Linear Constraints: Langevin Mixing and Information-Theoretic Guarantees Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval Expert Routing for Communication-Efficient MoE via Finite Expert Banks Contextual Memory-Enhanced Source Coding for Low-SNR Communications Realizable Bayes-Consistency for General Metric Losses Leveraging Code Automorphisms for Improved Syndrome-Based Neural Decoding A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning Dueling DDQN-Based Adaptive Multi-Objective Handover Optimization for LEO Satellite Networks The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy Optimization of CV-QKD Under Practical Constraints Benchmarking Wireless Representations: High-Dimensional vs. Compressed Embeddings for Efficiency and Robustness Real-Time Text Transmission via LLM-Based Entropy Coding over Fixed-Rate Channels SwiftChannel: Algorithm-Hardware Co-Design for Deep Learning-Based 5G Channel Estimation Evolving Token Communication with Parametric Memory Network Remote Action Generation: Remote Control with Minimal Communication The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions Stabilizing Private LASSO under Heterogeneous Covariates via Anisotropic Objective Perturbation Linear-Readout Floors and Threshold Recovery in Computation in Superposition Soft Graph Diffusion Transformer for MIMO Detection Hierarchical Federated Learning for Networked AI: From Communication Saving to Architecture-Aware Design Exponential families from a single KL identity MIFair: A Mutual-Information Framework for Intersectionality and Multiclass Fairness Diffusion-OAMP for Joint Image Compression and Wireless Transmission Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passing
Multi-Server Private Information Retrieval with Coded Sid...
Fatemeh Kazemi, Esmaeil Karimi, Anoosheh Heidarzadeh, Alex Sprin · 2019-06-22 · via cs.IT updates on arXiv.org

In this paper, we study the multi-server setting of the \emph{Private Information Retrieval with Coded Side Information (PIR-CSI)} problem. In this problem, there are $K$ messages replicated across $N$ servers, and there is a user who wishes to download one message from the servers without revealing any information to any server about the identity of the requested message. The user has a side information which is a linear combination of a subset of $M$ messages in the database. The parameter $M$ is known to all servers in advance, whereas the indices and the coefficients of the messages in the user's side information are unknown to any server \emph{a priori}. We focus on a class of PIR-CSI schemes, referred to as \emph{server-symmetric schemes}, in which the queries/answers to/from different servers are symmetric in structure. We define the \emph{rate} of a PIR-CSI scheme as its minimum download rate among all problem instances, and define the \emph{server-symmetric capacity} of the PIR-CSI problem as the supremum of rates over all server-symmetric PIR-CSI schemes. Our main results are as follows: (i) when the side information is not a function of the user's requested message, the capacity is given by ${(1+{1}/{N}+\dots+{1}/{N^{\left\lceil \frac{K}{M+1}\right\rceil -1}})^{-1}}$ for any ${1\leq M\leq K-1}$; and (ii) when the side information is a function of the user's requested message, the capacity is equal to $1$ for $M=2$ and $M=K$, and it is equal to ${N}/{(N+1)}$ for any ${3 \leq M \leq K-1}$. The converse proofs rely on new information-theoretic arguments, and the achievability schemes are inspired by our recently proposed scheme for single-server PIR-CSI as well as the Sun-Jafar scheme for multi-server PIR.