检索结果-内蒙古大学图书馆

Kernels for storage capacity and dual index coding

Journal of Combinatorial Theory. Series A 2025年 216卷

作者： Haviv, Ishay The Academic College of Tel Aviv-Yaffo Tel Aviv 61083 Israel

The storage capacity of a graph measures the maximum amount of information that can be stored across its vertices, such that the information at any vertex can be recovered from the information stored at its neighborhood. The study of this graph quantity is motivated by applications in distributed storage and by its intimate relations to the index coding problem from the area of network information theory. In the latter, one wishes to minimize the amount of information that has to be transmitted to a collection of receivers, in a way that enables each of them to discover its required data using some prior side information. In this paper, we initiate the study of the [Figure presented] and [Figure presented] problems from the perspective of parameterized complexity. We prove that the [Figure presented] problem parameterized by the solution size admits a kernelization algorithm producing kernels of linear size. We also provide such a result for the [Figure presented] problem, in the linear and non-linear settings, where it is parameterized by the dual value of the solution, i.e., the length of the transmission that can be saved using the side information. A key ingredient in the proofs is the crown decomposition technique due to Chor, Fellows, and Juedes [14,11]. As an application, we significantly extend an algorithmic result of Dau, Skachek, and Chee [13]. © 2025 Elsevier Inc.

关键词： index coding Kernelization Minrank Parameterized complexity Storage capacity

来源：评论

学校读者我要写书评

暂无评论

index coding in Vehicle to Vehicle Communication

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2020年第10期69卷 11926-11936页

作者： Pachat, Jesy Karat, Nujoom Sageer Deepthi, P. P. Rajan, B. Sundar Natl Inst Technol Elect & Commun Engn Dept Calicut 673601 Kerala India Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India

Vehicle to Vehicle (V2V) communication phase is an integral part of collaborative message dissemination in vehicular ad-hoc networks (VANETs). In this work, we apply index coding techniques to reduce the number of transmissions required for data exchange. The index coding problem has a sender, which tries to meet the demands of several receivers in a minimum number of transmissions. All these receivers have some prior knowledge of the messages, known as the side-information. In this work, we consider a particular case of the index coding problem, where multiple nodes want to share information among them. Under this set up, lower bound on the number of transmissions is established when the cardinality of side-information is the same. An optimal solution to achieve the bound in a special case of VANET scenario is presented. For this special case, we consider the link between the nodes to be error-prone, and in this setting, we construct optimal linear error correcting index codes.

关键词： index coding vehicle to vehicle communication

来源：评论

学校读者我要写书评

暂无评论

index coding Algorithms: Cooperative Caching and Delivery for F-RANs

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第11期71卷 12001-12015页

作者： Mostafa, Salwa Sung, Chi Wan Chan, Terence H. H. Xu, Guangping Univ Oulu Oulu Finland Menoufia Univ Fac Elect Engn Menoufia 6131567 Egypt City Univ Hong Kong Dept Elect Engn Hong Kong Peoples R China Univ South Australia Inst Telecommun Res Adelaide SA Australia Tianjin Univ Technol Sch Comp & Commun Engn Tianjin Peoples R China

In a Fog Radio Access Network (F-RAN), fog access points (F-APs) are equipped with caches that can store popular files during off-peak hours. Besides, they are densely deployed to have overlapping radio coverage so that requested files can be delivered cooperatively using beamforming. The bottleneck of the network is typically in the bandwidth-limited wireless fronthaul, which connects a cloud server to the F-APs. This work studies index coding design for cooperative caching and delivery in F-RAN to minimize fronthaul traffic and transmit energy. index coding algorithms are designed considering the cached content at the F-APs and the possibility of beamforming in the access network under coded and uncoded caching schemes. An optimal polynomial-time index coding algorithm for uncoded and repetition caching and an efficient heuristic for Maximum Distance Separable (MDS) coded caching are designed, and their superior performance is verified by simulations. The study is further extended to consider the tradeoff between the traffic load of the fronthaul link and the transmit energy consumed in the access network. At the expense of more fronthaul traffic, beamforming opportunities can be increased, significantly reducing energy consumption. Algorithms to achieve the tradeoff are crafted, and simulation results show that uncoded caching well balances the tradeoff.

关键词： Beamforming cooperative caching fronthaul traffic index coding transmit energy

来源：评论

学校读者我要写书评

暂无评论

index coding Capacity: How Far Can One Go With Only Shannon Inequalities?

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第6期61卷 3041-3055页

作者： Sun, Hua Jafar, Syed Ali Univ Calif Irvine Ctr Pervas Commun & Comp Dept Elect Engn & Comp Sci Irvine CA 92697 USA

An interference alignment perspective is used to identify the simplest instances (minimum possible number of edges in the alignment graph, not more than 2 interfering messages at any destination) of index coding problems where non-Shannon information inequalities are necessary for capacity characterization. In particular, this includes the first known example of a multiple unicast (one destination per message) index coding problem where non-Shannon information inequalities are shown to be necessary. The simplest multiple unicast example has 7 edges in the alignment graph and 11 messages. The simplest multiple groupcast (multiple destinations per message) example has 6 edges in the alignment graph, 6 messages, and 10 receivers. For both the simplest multiple unicast and multiple groupcast instances, the best outer bound based on only Shannon inequalities is 2/5, which is tightened to 11/28 by the use of the Zhang-Yeung non-Shannon type information inequality, and the linear capacity is shown to be 5/13 using the Ingleton inequality. Conversely, identifying the minimal challenging aspects of the index coding problem allows an expansion of the class of solved index coding problems up to (but not including) these instances.

关键词： Capacity index coding interference alignment non-shannon inequalities

来源：评论

学校读者我要写书评

暂无评论

index coding-An Interference Alignment Perspective

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第9期60卷 5402-5432页

作者： Maleki, Hamed Cadambe, Viveck R. Jafar, Syed A. Univ Calif Irvine Ctr Pervas Commun & Comp Irvine CA 92697 USA MIT Elect Res Lab Cambridge MA 02139 USA

The index coding problem is studied from an interference alignment perspective providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between the capacity of multiple unicast index coding (where each message is desired by exactly one receiver), and groupcast index coding (where a message can be desired by multiple receivers), which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with groupcast settings, where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message in the index coding problem are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate 1/(L + 1) per message when each destination desires at least L messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding.

关键词： index coding interference alignment network coding

来源：评论

学校读者我要写书评

暂无评论

Privacy in index coding: k-Limited-Access Schemes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第5期66卷 2625-2641页

作者： Karmoose, Mohammed Song, Linqi Cardone, Martina Fragouli, Christina Samsung Semicond Inc San Diego CA 92121 USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Minnesota Elect & Comp Engn Dept Minneapolis MN 55404 USA Univ Calif Los Angeles Elect & Comp Engn Dept Los Angeles CA 90095 USA

In the traditional index coding problem, a server employs coding to send messages to a set of clients within the same broadcast domain. Each client already has some messages as side information and requests a particular unknown message from the server. All clients learn the coding matrix so that they can decode and retrieve their requested data. Our starting observation comes from the work by Karmoose et al., which shows that learning the coding matrix can pose privacy concerns: it may enable a client to infer information about the requests and side information of other clients. In this paper, we mitigate this privacy concern by allowing each client to have limited access to the coding matrix. In particular, we design coding matrices so that each client needs only to learn some of (and not all) the rows to decode her requested message. We start by showing that this approach can indeed help mitigate that privacy concern. We do so by considering two different privacy metrics. The first one shows the attained privacy benefits based on a geometric interpretation of the problem. Differently, the second metric, referred to as maximal information leakage, provides upper bounds on: (i) the guessing power of the adversaries (i.e., curious clients) when our proposed approach is employed, and (ii) the effect of decreasing the number of accessible rows on the attained privacy. Then, we propose the use of $k$ -limited-access schemes: given an index coding scheme that employs $T$ transmissions, we create a $k$ -limited-access scheme with $T_{k}\geq T$ transmissions, and with the property that each client needs at most $k$ transmissions to decode her message. We derive upper and lower bounds on $T_{k}$ for all values of $k$ , and develop deterministic designs for these schemes, which are universal, i.e., independent of the coding matrix. We show that our schemes are order-optimal for some parameter regimes, and we propose heuristics that complement the universal schemes for the re

关键词： index coding privacy broadcasting k-limited-access scheme maximal information leakage

来源：评论

学校读者我要写书评

暂无评论

Single Uniprior index coding With Min-Max Probability of Error Over Fading Channels

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2017年第7期66卷 6050-6059页

作者： Thomas, Anoop Radhakumar, Kavitha Attada, Chandramouli Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India Qualcomm India Private Ltd Bangalore 560066 Karnataka India Intel Mobile Commun Bangalore 560066 Karnataka India

An index coding scheme in which the source (transmitter) transmits symbols over a wireless fading channel is considered. index codes with the transmitter using minimum number of transmissions are known as optimal index codes. Different optimal index codes give different performances in terms of probability of error in a fading environment, and this also varies from receiver to receiver. In this paper, we deal with optimal index codes, which minimizes the maximum probability of error among all the receivers. We identify a criterion for optimal index codes that minimizes the maximum probability of error among all the receivers. For a special class of index coding problems, we give an algorithm to identify optimal index codes whichminimize the maximum error probability. We illustrate our techniques and claims with simulation results leading to conclude that a careful choice among the optimal index codes will give a considerable gain in fading channels.

关键词： Fading broadcast channels index coding side information

来源：评论

学校读者我要写书评

暂无评论

Layered Space-Time index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第1期65卷 142-158页

作者： Huang, Yu-Chih Hong, Yi Viterbo, Emanuele Natarajan, Lakshmi Natl Taipei Univ Dept Commun Engn New Taipei 23741 Taiwan Monash Univ Dept Elect & Comp Syst Engn Melbourne Vic 3800 Australia IIT Hyderabad Dept Elect Engn Sangareddy 502285 India

Multicasting K independent messages via multiple-input multiple-output channels to multiple users where each user already has a subset of messages as side information is studied. A general framework of constructing layered space-time index coding (LSTIC) from a large class of space-time block codes (STBC), including perfect STBC, is proposed. We analyze the proposed LSTIC and show that it provides minimum determinant gains that are exponential with the amount of information contained in the side information for any possible side information. When constructed over a perfect STBC, the proposed LSTIC is itself a perfect STBC and hence many desired properties are preserved. To illustrate, we construct LSTIC over the following well-known STBCs: Golden code;3x3, 4x4, and 6x6 perfect STBCs;and Alamouti code. Simulation results show that the obtained side information gain can be well predicted by our analysis.

关键词： index coding broadcast channels side information space-time block codes MIMO channel

来源：评论

学校读者我要写书评

暂无评论

A Rate-Distortion Approach to index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第11期62卷 6359-6378页

作者： Unal, Sinem Wagner, Aaron B. Cornell Univ Sch Elect & Comp Engn Ithaca NY 14853 USA

We approach index coding as a special case of rate-distortion with multiple receivers, each with some side information about the source. Specifically, using techniques developed for the rate-distortion problem, we provide two upper bounds and one lower bound on the optimal index coding rate. The upper bounds involve specific choices of the auxiliary random variables in the best existing scheme for the rate-distortion problem. The lower bound is based on a new lower bound for the general rate-distortion problem. The bounds are shown to coincide for a number of (groupcast) index coding instances, including all instances for which the number of decoders does not exceed three.

关键词： index coding rate distortion multiple decoders side information

来源：评论

学校读者我要写书评

暂无评论

Hardness of Linear index coding on Perturbed Instances

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第2期70卷 1388-1396页

作者： Chawin, Dror Haviv, Ishay Acad Coll Tel Aviv Yaffo Sch Comp Sci IL-61083 Tel Aviv Israel

The index coding problem is concerned with the amount of information that a sender has to transmit to multiple receivers in a way that enables each of them to retrieve its requested data relying on prior side information. For linear index coding, the problem is characterized by the minrank parameter of a graph that represents the side information map of the receivers. Previous work has shown that it is $\mathsf {NP}$ -hard to determine the minrank parameter of graphs. In this work, we study the computational complexity of the minrank parameter on perturbed instances, obtained from worst-case instances by a random extension of the side information available to the receivers. This setting is motivated by applications of index coding, in which the side information is accumulated via repeated transmissions that suffer from loss of data due to noisy communication or storage capacity. We prove that determining the minrank parameter remains computationally hard on perturbed instances. Our contribution includes an extension of several hardness results of the minrank parameter to the perturbed setting as well as a general technique for deriving the hardness of the minrank parameter on perturbed instances from its hardness on worst-case instances.

关键词： index coding minrank hardness perturbed instances

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：