Bounds on the Communication Rate Needed to Achieve SK Capacity in the Hypergraphical Source Model

Mukherjee, Chan, Kashyap, Zhou · cs.IT,math.IT · 2016-01-28 · 原文

In the multiterminal source model of Csisz\text{á}r and Narayan, the communication complexity, R_{\text{SK}}, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to R_{\text{SK}} is given by R_{\text{CO}}, which is the minimum rate of communication required for \emph{omniscience}. In this paper we derive a better upper bound to R_{\text{SK}} for the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on R_{\text{SK}}. This bound, however, is not tight, as demonstrated by a counterexample.

🔮 让 ChatGPT 全网深度追问

讲义

讲义·推断依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。

1. 人话版

An obvious upper bound to R_{\text{SK}} is given by R_{\text{CO}}, which is the minimum rate of communication required for \emph{omniscience}.

2. 领域脉络

本文类目：cs.IT、math.IT，属于其所在研究脉络的最新进展。

3. 机制拆解

In this paper we derive a better upper bound to R_{\text{SK}} for the hypergraphical source model, which is a special instance of the multiterminal source model.

The upper bound is based on the idea of fractional removal of hyperedges.

It is further shown that this upper bound can be computed in polynomial time.

4. 证据与数字

摘要未给出量化结果——留意原文的实验与数据。

5. 反例与边界

This bound, however, is not tight, as demonstrated by a counterexample.

6. 跨领域连接与意外收获

横跨 2 个类目（cs.IT、math.IT），关注其在你兴趣板块间的迁移面。

7. 可复用方法

把本文机制与你手头项目对照，找一个两周内能验证的最小实验。

8. 术语表

精读时把不熟的术语记入此处，作为下次回忆的锚点。