Task-Based Solutions to Embedded Index Coding
Task-Based Solutions to Embedded Index Coding
复制标题
基于任务的嵌入式索引编码解决方案
DOI：
10.1109/tit.2020.2990822
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
I. Haviv
中科院分区：
文献类型：
--
作者：
I. Haviv
在索引编码问题中，发送者持有一条消息 <inline-formula> <tex-math notation="LaTeX">$x \in \{0,1\}^{n}$ </tex-math></inline-formula> 并希望将信息广播到 <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> 接收者，从而使<inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula>接收器检索<inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula>位<inline-formula> <tex-math notation="LaTeX">$x_{i}$ </tex-math></内联公式>。每个接收器都有包含 <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> 位子集的先验辅助信息，目标是最小化通过广播通道发送的信息的长度。 Porter 和 Wootters 最近引入了<斜体>嵌入式索引编码</斜体>模型，其中接收者也扮演发送者的角色，目标是最小化其广播信息的总长度。如果每个接收器仅根据其中一个接收器提供的信息检索其位，则嵌入式索引代码被称为<斜体>基于任务</斜体>。本文研究了基于任务的限制对线性嵌入索引编码的影响。结果表明，对于某些辅助信息映射，存在长度比任何基于任务的嵌入索引码小二次方的线性嵌入索引码。结果在乘法常数范围内达到两个量之间的最大可能差距。证明是通过显式构造进行的，分析涉及谱技术。
In the <italic>index coding</italic> problem a sender holds a message <inline-formula> <tex-math notation="LaTeX">$x \in \{0,1\}^{n}$ </tex-math></inline-formula> and wishes to broadcast information to <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> receivers in a way that enables the <inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula>th receiver to retrieve the <inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula>th bit <inline-formula> <tex-math notation="LaTeX">$x_{i}$ </tex-math></inline-formula>. Every receiver has prior side information comprising a subset of the bits of <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula>, and the goal is to minimize the length of the information sent via the broadcast channel. Porter and Wootters have recently introduced the model of <italic>embedded index coding</italic>, where the receivers also play the role of the sender and the goal is to minimize the total length of their broadcast information. An embedded index code is said to be <italic>task-based</italic> if every receiver retrieves its bit based only on the information provided by one of the receivers. This paper studies the effect of the task-based restriction on linear embedded index coding. It is shown that for certain side information maps there exists a linear embedded index code of length quadratically smaller than that of any task-based embedded index code. The result attains, up to a multiplicative constant, the largest possible gap between the two quantities. The proof is by an explicit construction and the analysis involves spectral techniques.
随机图的 Minrank
影响因子：
2.5
作者：
Golovnev, Alexander;Regev, Oded;Weinstein, Omri
通讯作者：
Weinstein, Omri
影响因子：
2.5
作者：
Porter, Alexandra;Wootters, Mary
通讯作者：
Wootters, Mary