論文の概要: Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems

• arxiv url: http://arxiv.org/abs/2510.25736v1
• Date: Wed, 29 Oct 2025 17:40:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-30 15:50:45.89291
• Title: Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems
• Title（参考訳）: グラフベースレプリケーションシステムにおける対称PIRの完全共通乱数レプリケーションの効果
• Authors: Shreya Meel, Sennur Ulukus,
• Abstract要約: データベースの複製を単純なグラフでモデル化した環境で、対称なプライベート情報検索の問題を再考する。 メッセージとは独立して、すべてのサーバに共通するランダム性を共有させます。 所望シンボル数とダウンロードシンボル数の最大比であるSPIR容量の改善を定量化する。
• 参考スコア（独自算出の注目度）: 43.914623898157856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of symmetric private information retrieval (SPIR) in settings where the database replication is modeled by a simple graph. Here, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. To satisfy the requirement of database privacy, we let all the servers share some common randomness, independent of the messages. We aim to quantify the improvement in SPIR capacity, i.e., the maximum ratio of the number of desired and downloaded symbols, compared to the setting with graph-replicated common randomness. Towards this, we develop an algorithm to convert a class of PIR schemes into the corresponding SPIR schemes, thereby establishing a capacity lower bound on graphs for which such schemes exist. This includes the class of path and cyclic graphs for which we derive capacity upper bounds that are tighter than the trivial bounds given by the respective PIR capacities. For the special case of path graph with three vertices, we identify the SPIR capacity to be $\frac{1}{2}$.
• Abstract（参考訳）: データベース複製を単純なグラフでモデル化した環境では、対称プライベート情報検索(SPIR)の問題を再考する。 ここでは、各頂点がサーバに対応し、メッセージが2つのサーバで複製される。 データベースのプライバシの要件を満たすため、すべてのサーバが、メッセージとは独立して、何らかの共通なランダム性を共有できるようにします。 本研究では,SPIRの容量向上,すなわち所望シンボル数とダウンロードシンボル数の最大比の定量化を目的としている。 そこで我々は,PIRスキームのクラスを対応するSPIRスキームに変換するアルゴリズムを開発し,そのようなスキームが存在するグラフ上でのキャパシティを低く設定する。 これには、それぞれのPIR容量によって与えられる自明な境界よりも厳密な容量上界を導出するパスグラフと巡回グラフのクラスが含まれる。 3つの頂点を持つパスグラフの特別な場合、SPIRの容量は$\frac{1}{2}$である。

関連論文リスト

• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
  単純なグラフでモデル化された複製されたデータベース上の対称プライベート情報検索。 本研究では,SPIRを実現するのに必要なサーバ側の共通乱数性も,そのグラフに従ってサーバに複製されるような設定について考察する。
  論文  参考訳（メタデータ） (2025-07-23T17:51:08Z)
• New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage [39.51026717015587]
  グラフベースおよびマルチグラフベースの複製システムにおけるプライベート情報検索(PIR)の問題について検討する。 このような系に対するPIR容量の上限を導出し、これらの境界に近づくPIRスキームを構築する。
  論文  参考訳（メタデータ） (2025-04-29T16:05:42Z)
• Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
  多重グラフを用いた複製システムにおけるプライベート情報検索問題について考察する。 我々の目標は、$r$-multigraphのPIR容量の上下境界を確立することです。
  論文  参考訳（メタデータ） (2025-01-29T18:48:22Z)
• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  共有インタラクション(SI)は、複数のノード間のノードのコントリビューションとインタラクションを定量化する。 GNNアーキテクチャを利用して、ノード埋め込みにおける相互作用の構造がグラフ予測のために保存されていることを示す。 任意の順序SIを正確に計算するための効率的なアプローチであるGraphSHAP-IQを導入する。
  論文  参考訳（メタデータ） (2025-01-28T13:37:44Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。 提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
  論文  参考訳（メタデータ） (2021-07-05T11:41:16Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。