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

JOURNAL OF GRAPH THEORY 2023年第2期104卷 387-419页

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

An orthogonal representation of a graph G over a field F is an assignment of a vector uv is an element of F' in to every vertex v of G, such that < u(v),u(v))not equal 0 for every vertex v and < uv,uv '=0 whenever v and v ' are adjacent in G. The locality of the orthogonal representation is the largest dimension of a subspace spanned by the vectors associated with a closed neighborhood in the graph. We introduce a novel graph parameter, called the local orthogonality dimension, defined for a given graph G and a given field F, as the smallest possible locality of an orthogonal representation of G over F. This is a local variant of the well-studied orthogonality dimension of graphs, introduced by Lovasz, analogously to the local variant of the chromatic number introduced by Erdos et al. We investigate the usefulness of topological methods for proving lower bounds on the local orthogonality dimension. Such methods are known to imply tight lower bounds on the chromatic number of several graph families of interest, such as Kneser graphs and Schrijver graphs. We prove that graphs for which topological methods imply a lower bound of t on their chromatic number have local orthogonality dimension at least left ceiling t/2 right ceiling +1 over every field, strengthening a result of Simonyi and Tardos on the local chromatic number. We show that for certain graphs this lower bound is tight, whereas for others, the local orthogonality dimension over the reals is equal to the chromatic number. More generally, we prove that for every complement of a line graph, the local orthogonality dimension over R coincides with the chromatic number. This strengthens a recent result by Daneshpajouh, Meunier, and Mizrahi, who proved that the local and standard chromatic numbers of these graphs are equal. As another extension of their result, we prove that the local and standard chromatic numbers are equal for some additional graphs, from the family of Kneser graphs. We also study the computati

关键词： algebraic topology index coding local chromatic number local orthogonality dimension minrank

来源：评论

学校读者我要写书评

暂无评论

Binary Informed Source Codes and index Codes Using Certain Near-MDS Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2018年第5期66卷 2181-2190页

作者： Thomas, Anoop Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India

A source coding problem in which a central source has to satisfy the demands of several receivers, with each receiver having some subset of the messages (side-information) held by the source is considered. The source has knowledge of only the cardinality of the side-information at each receiver. The encoding scheme used by the source to transmit at a higher throughput is referred to as an informed source code. A technique to obtain informed source codes by using l-th Near Maximum Distance Separable (Near-MDS) Codes is presented. The advantage of using l-th Near-MDS codes is the reduction in field size required. For certain informed source coding problems, the code obtained from l-th Near-MDS codes is shown to be of the minimum length under certain field size restrictions. The same technique can be used for a given index coding problem to obtain index codes. The index codes obtained through this technique are optimal for, but not limited to, special cases of index coding problems discussed in the paper. Finding an optimal solution to a general index coding problem is NP hard and this technique helps in finding binary suboptimal solutions. Using the Gilbert-Varshamov bound, an upper bound on the lengths of optimal binary informed source codes is obtained.

关键词： index coding informed source codes MDS codes side-information

来源：评论

学校读者我要写书评

暂无评论

Fundamental Limits of Topology-Aware Shared-Cache Networks

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第4期70卷 2538-2565页

作者： Parrinello, Emanuele Bazco-Nogueras, Antonio Elia, Petros EURECOM Commun Syst Dept F-06904 Sophia Antipolis France CEVA F-06410 Biot France IMDEA Networks Inst Leganes 28918 Madrid Spain

This work studies a well-known shared-cache coded caching scenario where each cache can serve an arbitrary number of users. We analyze the case where there is some knowledge about such number of users (i.e., the topology) during the content placement phase. Under the assumption of regular placement and a cumulative cache size that can be optimized across the different caches, we derive the fundamental limits of performance by introducing a novel cache-size optimization and placement scheme and a novel information-theoretic converse. The converse employs new index coding techniques to bypass traditional uniformity requirements, thus finely capturing the heterogeneity of the problem, and it provides a new approach to handle asymmetric settings. The new fundamental limits reveal that heterogeneous topologies can in fact outperform their homogeneous counterparts where each cache is associated to an equal number of users. These results are extended to capture the scenario of topological uncertainty where the perceived/estimated topology does not match the true network topology. This scenario is further elevated to the stochastic setting where the user-to-cache association is random and unknown, and it is shown that the proposed scheme is robust to such noisy or inexact knowledge on the topology.

关键词： Resource management Topology Libraries Servers Optimization Network topology indexes Coded caching shared cache topology-aware index coding combinatorics

来源：评论

学校读者我要写书评

暂无评论

Order-Optimal Rate of Caching and Coded Multicasting With Random Demands

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第6期63卷 3923-3949页

作者： Ji, Mingyue Tulino, Antonia M. Llorca, Jaime Caire, Giuseppe Univ Utah Dept Elect & Comp Engn Salt Lake City UT 84112 USA Univ Naples Federico II DIETI Dept I-80138 Naples Italy Nokia Bell Labs Holmdel NJ 07733 USA Tech Univ Berlin EECS Dept D-10623 Berlin Germany

We consider the canonical shared link caching network formed by a source node, hosting a library of m information messages (files), connected via a noiseless multicast link to n user nodes, each equipped with a cache of size M files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as rate (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting.

关键词： Content distribution coded caching random demands index coding order optimal rate

来源：评论

学校读者我要写书评

暂无评论

Private Information Retrieval With Side Information

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第4期66卷 2032-2043页

作者： Kadhe, Swanand Garcia, Brenden Heidarzadeh, Anoosheh El Rouayheb, Salim Sprintson, Alex Texas A&M Univ ECE Dept College Stn TX 77843 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Epic Syst Corp Verona WI 53593 USA Rutgers State Univ Dept Elect & Comp Engn New Brunswick NJ 08901 USA

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of K independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of M messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information;(ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is K-M messages, and in the second scenario it is [\lceil K/(M+1)]r messages, which should be compared to K messages-the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

关键词： Servers Privacy indexes Data privacy Encoding Information retrieval Private information retrieval information-theoretic privacy index coding

来源：评论

学校读者我要写书评

暂无评论

Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree Structures

引用

ALGORITHMICA 2015年第1期71卷 152-180页

作者： Dau, Son Hoang Chee, Yeow Meng Nanyang Technol Univ Sch Phys & Math Sci Div Math Sci Singapore 637371 Singapore

The min-rank of a graph was introduced by Haemers (Algebr. Methods Graph Theory 25:267-272, 1978) to bound the Shannon capacity of a graph. This parameter of a graph has recently gained much more attention from the research community after the work of Bar-Yossef et al. (in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197-206, 2006). In their paper, it was shown that the min-rank of a graph characterizes the optimal scalar linear solution of an instance of the index coding with Side Information (ICSI) problem described by the graph . It was shown by Peeters (Combinatorica 16(3):417-431, 1996) that computing the min-rank of a general graph is an NP-hard problem. There are very few known families of graphs whose min-ranks can be found in polynomial time. In this work, we introduce a new family of graphs with efficiently computed min-ranks. Specifically, we establish a polynomial time dynamic programming algorithm to compute the min-ranks of graphs having simple tree structures. Intuitively, such graphs are obtained by gluing together, in a tree-like structure, any set of graphs for which the min-ranks can be determined in polynomial time. A polynomial time algorithm to recognize such graphs is also proposed.

关键词： index coding Network coding Min-rank Tree structure Dynamic programming Polynomial time

来源：评论

学校读者我要写书评

暂无评论

On the Hardness of Approximating the Network coding Capacity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 1008-1014页

作者： Langberg, Michael Sprintson, Alex Open Univ Israel Div Comp Sci IL-43107 Raanana Israel Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA

This work addresses the computational complexity of achieving the capacity of a general network coding instance. It has been shown [Lehman and Lehman, SODA 2005] that determining the "scalar linear" capacity of a general network coding instance is NP-hard. In this paper we address the notion of approximation in the context of both linear and nonlinear network coding. Loosely speaking, we show that given an instance of the general network coding problem of capacity C, constructing a code of rate alpha C for any universal (i.e., independent of the size of the instance) constant alpha <= 1 is "hard". Specifically, finding such network codes would solve a long standing open problem in the field of graph coloring. Our results refer to scalar linear, vector linear, and nonlinear encoding functions and are the first results that address the computational complexity of achieving the network coding capacity in both the vector linear and general network coding scenarios. In addition, we consider the problem of determining the (scalar) linear capacity of a planar network coding instance (i.e., an instance in which the underlying graph is planar). We show that even for planar networks this problem remains NP-hard.

关键词： Approximation capacity complexity index coding network coding

来源：评论

学校读者我要写书评

暂无评论

Wireless index Coded Transmission by Spatial Multiplexing With Multiple Antennas

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2021年第5期70卷 5104-5108页

作者： Son, Kyungrak Lee, Jung Hoon Choi, Wan Korea Adv Inst Sci & Technol KAIST Sch Elect Engn Daejeon 34141 South Korea Hankuk Univ Foreign Studies HUFS Dept Elect Engn Yongin 17035 South Korea Hankuk Univ Foreign Studies HUFS Appl Commun Res Ctr Yongin 17035 South Korea Seoul Natl Univ SNU Inst New Media & Commun Seoul 08826 South Korea Seoul Natl Univ SNU Dept Elect & Comp Engn Seoul 08826 South Korea

index coding, a.k.a. coded multicasting, is one of the promising transmission schemes that can reduce the number of transmissions by leveraging the stored data in the users' memory. With multiple antennas, index coding gain can be further multiplied by spatially multiplexing but joint design of index code and beamforming has not been addressed well in literature. This paper figures out the gain of spatially multiplexed index code by jointly designing the multicast beamformer and index code. Since the optimal joint design problem itself is NP-hard, we take a two-step approach. At the first step, for an arbitrary index code, conjugate gradient-based multi-group multicast beamforming is designed. At the second step, the index code minimizing the total transmission time is selected. Our simulation results exhibit a substantial gain of spatially multiplexed index code by the proposed scheme.

关键词： indexes Array signal processing Encoding Multiplexing MISO communication Signal to noise ratio Interference index coding content delivery multicast beamforming transmission time minimization

来源：评论

学校读者我要写书评

暂无评论

An Optimal Error Correction Scheme for the Shuffle Phase of a MapReduce Distributed Computing System

引用

IEEE COMMUNICATIONS LETTERS 2021年第12期25卷 3765-3769页

作者： Mahesh, Anjana A. Karat, Nujoom Sageer Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India Indian Inst Technol Dept Elect Engn Mumbai 400076 Maharashtra India

The MapReduce model of distributed computation accomplishes a task in three phases - two computation phases-Map and Reduce, with a communication phase - Shuffle, happening in between. This letter looks at the distributed communication problem in the shuffle phase with the assumption that the links through which the computing nodes exchange information is error-prone. Under this assumption, an optimal linear error-correcting transmission scheme is designed using index coding techniques.

关键词： indexes Encoding Distributed computing Computational modeling Task analysis Receivers Error correction codes Distributed computing error correction index coding MapReduce

来源：评论

学校读者我要写书评

暂无评论

Polar Codes for Informed Receivers

引用

IEEE COMMUNICATIONS LETTERS 2018年第10期22卷 2000-2003页

作者： Huang, Yu-Chih Shieh, Shin-Lin Natl Taipei Univ Dept Commun Engn New Taipei 237 Taiwan

The problem of sending independent messages to a receiver which already has been informed a subset of messages as side information is studied. Which messages are available at the receiver is assumed to be oblivious to the transmitter. A simple yet powerful construction of codes for informed receivers based on polar codes is proposed to efficiently and fairly convert side information into reduction in probability of errors for any message side information. Compared with existing designs based on codes on graph or algebraic codes, the proposed construction is both conceptually and practically simple. Moreover, the codes inherit many good properties of polar codes, including explicit construction and low-complexity encoding and decoding scaling such as O(N log N) where N is the blocklength. Extensions to high-order modulation and block fading channels are also proposed. Simulation results indicate that for every side information configuration, the proposed codes can convert side information into reduction in signal-to-noise ratio of roughly 6 dB/bit at hit error rate of 10(-5) under additive white Gaussian noise channel or block fading channel.

关键词： index coding polar codes side information

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：