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

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Alistarh, Dan Aspnes, James Gilbert, Seth Guerraoui, Rachid Ecole Polytech Fed Lausanne Lausanne Switzerland NUS Singapore Singapore Yale Univ New Haven CT 06520 USA

ISBN: (纸本)9780769545714

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into any namespace of size sub-exponential in k, where k is the number of participants. This bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic fetch-and-increment registers, queues and stacks. The proof of the bound is interesting in its own right, for it relies on the first reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement our individual bound with a global lower bound of Omega(k log(k/c)) on the total step complexity of renaming into a namespace of size c k, for any c >= 1. This applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter and fetch-and-increment implementations, all tight within logarithmic factors.

关键词： Adaptation models Adaptive systems Complexity theory Radiation detectors Registers Sorting Wires approximation theory computational complexity deterministic algorithms deterministic fetch and increment queues deterministic fetch and increment register det

来源：评论

学校读者我要写书评

暂无评论

Approximate inference in Bayesian networks using binary probability trees

Approximate inference in Bayesian networks using binary prob...

引用

10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty

作者： Cano, Andres Gomez-Olmedo, Manuel Moral, Serafin Univ Granada Dept Comp Sci & Artificial Intelligence Higher Tech Sch Comp Sci & Telecommun E-18071 Granada Spain

The present paper introduces a new kind of representation for the potentials in a Bayesian network: binary probability trees. They enable the representation of context-specific independences in more detail than probability trees. This enhanced capability leads to more efficient inference algorithms for some types of Bayesian networks. This paper explains the procedure for building a binary probability tree from a given potential, which is similar to the one employed for building standard probability trees. It also offers a way of pruning a binary tree in order to reduce its size. This allows us to obtain exact or approximate results in inference depending on an input threshold. This paper also provides detailed algorithms for performing the basic operations on potentials (restriction, combination and marginalization) directly to binary trees. Finally, some experiments are described where binary trees are used with the variable elimination algorithm to compare the performance with that obtained for standard probability trees. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Bayesian networks inference Approximate computation Variable elimination algorithm deterministic algorithms Probability trees

来源：评论

学校读者我要写书评

暂无评论

Entanglement Cost of Implementing Controlled-Unitary Operations

引用

Physical Review Letters 2011年第18期107卷 180501-180501页

作者： Akihito Soeda Peter S. Turner Mio Murao Graduate School of Science The University of Tokyo 7-3-1 Hongo Bunkyo-ku Tokyo Japan Centre for Quantum Technologies National University of Singapore 3 Science Drive 2 117543 Singapore Singapore Institute for Nano Quantum Information Electronics The University of Tokyo 4-6-1 Komaba Meguro-ku Tokyo Japan

We investigate the minimum entanglement cost of the deterministic implementation of two-qubit controlled-unitary operations using local operations and classical communication (LOCC). We show that any such operation can be implemented by a three-turn LOCC protocol, which requires at least 1 ebit of entanglement when the resource is given by a bipartite entangled state with Schmidt number 2. Our result implies that there is a gap between the minimum entanglement cost and the entangling power of controlled-unitary operations. This gap arises due to the requirement of implementing the operations while oblivious to the identity of the inputs.

关键词： UNITARY operators BIPARTITE graphs deterministic algorithms QUANTUM theory HILBERT space

来源：评论

学校读者我要写书评

暂无评论

Transmission Strategies for Gaussian Relay Networks Obtained from deterministic Models

Transmission Strategies for Gaussian Relay Networks Obtained...

引用

IEEE Global Telecommunications Conference (GLOBECOM 2010)

作者： Schrammar, Nicolas Skoglund, Mikael KTH Royal Inst Technol Sch Elect Engn Stockholm Sweden KTH Royal Inst Technol ACCESS Linnaeus Ctr Stockholm Sweden

ISBN: (纸本)9781424456383

A constant gap between the deterministic model of a class of a wireless relay network and its Gaussian model counterpart is derived. The method is constructive in the sense that a transmission solution in the deterministic model that obeys certain constraints can directly be translated into a transmission in the Gaussian model. We show that the rate in the Gaussian model is at most a constant gap below the rate in the deterministic model, and we derive an upper bound on this gap.

关键词： Gaussian model Gaussian processes data communication deterministic algorithms deterministic models radiocommunication relays transmission strategy wireless relay network

来源：评论

学校读者我要写书评

暂无评论

An Efficient Cluster Expansion Method for Binary Solid Solutions: Application to the Halite-Silvite, NaCl-KCl, System

引用

THEORETICAL AND COMPUTATIONAL METHODS IN MINERAL PHYSICS: GEOPHYSICAL APPLICATIONS 2010年第1期71卷 413-436页

作者： Vinograd, Victor Winkler, Bjoern Goethe Univ Frankfurt Inst Geosci Frankfurt Germany

ISBN: (纸本)9780939950850

The system NaCl-KCl is used as an example to introduce the reader to a variety of concepts, which form the modern solid solution theory. The chapter starts with the discussion of the chemical stress both end members experience in the process of mixing. This stress is treated as a homogeneous deformation of the end members within the concept of the virtual crystal approximation, VCA. It is shown that the VCA predicts the existence of a positive excess enthalpy in the NaCl-KCl solid solution, but drastically overestimates its magnitude. The inaccuracy of the VCA is attributed to its failure to describe local relaxations. Further, the local relaxations are linked to the effects of intracrystalline reactions of NaNa + KK = 2NaK type, and it is shown that the excess enthalpy can be written as a sum of such interactions acting at various distances within the supercell. The decomposition of the enthalpy of mixing into pairwise interactions is then discussed in the relation to a more general cluster expansion technique, which considers effective interactions from clusters of various sizes and shapes including many-body interactions. Then we argue that a wide range of materials interesting for geosciences can be described within the concept of pairwise interactions only and introduce the supercell expansion method dealing with the effective pairwise interactions. It is then shown that the calculation of the effective pairwise interactions can be performed with different methods. The traditional approach consisting in the calculation of the static energies of a large number of randomly varied structures and solving for the pairwise interactions with the least squares method is compared to a deterministic algorithm, which is based on the consideration of the excess energies of the structures with double defects inserted at all possible pairwise distances within the supercell. This Double Defect Method, DDM, is then applied to the system NaCl-KCl. The effective interactions obt

关键词： homogeneous deformation Value Control Amplifier Monte Carlo technique deterministic algorithms Free energy solid solution Pairwise FREE ENERGY OF MIXING Enthalpy end member

来源：评论

学校读者我要写书评

暂无评论

Peeling Algorithm for Custom Instruction Identification

Peeling Algorithm for Custom Instruction Identification

引用

IEEE Asia Pacific Conference on Circuit and System (APCCAS)

作者： Zhao, Kang Bian, Jinian Tsinghua Univ EDA Lab Dept Comp Sci & Technol Beijing 100084 Peoples R China

ISBN: (纸本)9781424474561

To speedup the custom instruction identification for the application specific instruction-set processor (ASIP), this paper proposes a peeling algorithm. It starts with the maximal valid pattern, and then gets a set of valid sub-patterns through deleting the source and sink respectively. Furthermore, a local priority is proposed for the exhaustive pruning. The final experiment indicates a distinct speedup compared to the fastest deterministic algorithm.

关键词： instruction Customs Customization Speeding deterministic algorithms algorithms Valid

来源：评论

学校读者我要写书评

暂无评论

Recursive Probability Trees for Bayesian Networks

Recursive Probability Trees for Bayesian Networks

引用

13th Conference of the Spanish-Association-for-Artificial-Intelligence (CAEPIA 2009)

作者： Cano, Andres Gomez-Olmedo, Manuel Moral, Serafin Perez-Ariza, Cora B. Univ Granada Dept Comp Sci & Artificial Intelligence E-18071 Granada Spain

ISBN: (纸本)9783642142635

This paper proposes a new data structure for representing potentials. Recursive probability trees are a generalization of probability trees. Both structures are able to represent context-specific independencies, but the new one is also able to hold a potential in a factorized way. This new structure can represent some kinds of potentials in a more efficient way than probability trees, and it can be the case that only recursive trees are able to represent certain factorizations. Basic operations for inference in Bayesian networks can be directly performed upon recursive probability trees.

关键词： Bayesian networks inference approximate computation deterministic algorithms probability trees

来源：评论

学校读者我要写书评

暂无评论

Pairwise Test Set Calculation using k-partite Graphs

Pairwise Test Set Calculation using k-partite Graphs

引用

International Conference on Software Maintenance

作者： Salecker, Elke Glesner, Sabine Berlin Inst Technol TU Berlin Berlin Germany

ISBN: (纸本)9781424486298

of input values and can be detected using pairwise test sets that cover each pair of input values. The generation of pairwise test sets with a minimal size is an NP-complete problem which implies that many algorithms are either expensive or based on a random process. In this paper we present a deterministic algorithm that exploits our observation that the pairwise testing problem can be modeled as a k-partite graph problem. We calculate the test set using well investigated graph algorithms that take advantage of properties of k-partite graphs. We present evaluation results that prove the applicability of our algorithm and discuss possible improvement of our approach.

关键词： NP-complete problem computational complexity deterministic algorithm deterministic algorithms fault diagnosis graph theory k-partite graph problem k-partite graphs pairwise test set calculation pairwise testing problem program testing random process software fault tolerance software faults

来源：评论

学校读者我要写书评

暂无评论

A Multi-Objective Risk-Based Approach for Airlift Task Scheduling Using Stochastic Bin Packing

A Multi-Objective Risk-Based Approach for Airlift Task Sched...

引用

2010 IEEE World Congress on Computational Intelligence

作者： Zhao, Wenjing Liu, Jing Abbass, Hussein A. Bender, Axel Univ New South Wales Australian Def Force Acad Sch Engn & Informat Technol Sydney NSW 2052 Australia Def Sci & Technol Org Canberra ACT Australia

ISBN: (纸本)9781424481262

An important aspect of airlift problems is to find the smallest fleet of aircraft to move cargo from one or more locations to a destination. In critical airlift operations, such as emergency evacuations, disaster relief and defence operations, a compromise needs to be struck between minimizing the time needed for completing all tasks and minimizing the size of the fleet. Usually, the time to complete a task is stochastic. A deterministic model, therefore, will under-estimate fleet size which results in increased levels of risk to achieve the overall airlift mission. In this paper, we introduce a stochastic version of the two-dimensional bin packing problem. We test a number of objective functions to measure different levels of risk. We then use an evolutionary multi-objective algorithm to solve a number of test problems. Analysis demonstrates that the different risk functions and level of variability/uncertainty in performing each task affect solutions non-linearly. Moreover, the multi-objective approach provides the analyst with an estimate of the range of risk;thus solutions can be selected based on criticality of meeting airlift demands.

关键词： aircraft aircraft airlift task scheduling bin packing deterministic algorithms deterministic model freight handling multi-objective risk-based approach objective functions risk analysis scheduling stochastic bin packing stochastic processes two-dimensional bin packing problem

来源：评论

学校读者我要写书评

暂无评论

Clasas: A key-store for the Cloud

Clasas: A key-store for the Cloud

引用

18th Annual IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS 2010

作者： Thomas Schwarz, S.J. Long, Darrell D. E. Universidad Católica del Uruguay Montevideo Uruguay University of California Santa Cruz CA United States

ISBN: (纸本)9780769541976

We propose Clasas (from the Castilian "Claves seguras" for "secure keys"), a key-store for distributed storage such in the Cloud. The security of Clasas derives from breaking keys into K shares and storing the key shares at many different sites. This provides both a probabilistic and a deterministic guarantee against an adversary trying to obtain keys. The probabilistic guarantee is based on a combinatorial explosion, which forces an adversary to subvert a very large portion of the storage sites for even a minute chance of obtaining a key. The deterministic guarantee stems from the use of LH* distributed linear hashing. Our use of the LH* addressing rules insures that no two key shares (belonging to the same key) are ever, even in transit, stored at the same site. Consequentially, an adversary has to subvert at least K sites. In addition, even an insider with extensive administrative privileges over many of the sites used for key storage is prevented from obtaining access to any key. Our key-store uses LH* or its scalable availability derivate, LH*RS to distribute key shares among a varying number of storage sites in a manner transparent to its users. While an adversary faces very high obstacles in obtaining a key, clients or authorized entities acting on their behalf can access keys with a very small number of messages, even if they do not know all sites where key shares are stored. This allows easy sharing of keys, rekeying, and key revocation. © 2010 IEEE.

关键词： Clasas Internet LH* addressing rule LH* distributed linear hashing combinatorial explosion combinatorial mathematics cryptography deterministic algorithms deterministic guarantee distributed storage key revocation key sharing key store probabilistic guarantee probability rekeying

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：