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

Adversary lower bounds for nonadaptive quantum algorithms

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第5期76卷 347-355页

作者： Koiran, Pascal Landes, Juergen Portier, Natacha Yao, Penghui Univ Lyon Ecole Normale Super Lyon LIP CNRSUMR 5668INRIA Lyon France Univ Manchester Sch Math Manchester M13 9PL Lancs England Chinese Acad Sci State Key Lab Comp Sci Beijing 100864 Peoples R China

We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the "1-to-1 versus 2-to-1" problem and of Hidden Translation. In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Query complexity Quantum algorithms Lower bounds Adversary method nonadaptive algorithms

来源：评论

学校读者我要写书评

暂无评论

A survey on nonadaptive group testing algorithms through the angle of decoding

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2008年第1期15卷 49-59页

作者： Chen, Hong-Bin Hwang, Frank K. Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan

Group testing, sometimes called pooling design, has been applied to a variety of problems such as blood testing, multiple access communication, coding theory, among others. Recently, screening experiments in molecular biology has become the most important application. In this paper, we review several models in this application by focusing on decoding, namely, giving a comparative study of how the problem is solved in each of these models.

关键词： group testing pooling designs nonadaptive algorithms

来源：评论

学校读者我要写书评

暂无评论

nonadaptive Deterministic Asynchronous Conflict Resolution

引用

IEEE COMMUNICATIONS LETTERS 2018年第6期22卷 1168-1171页

作者： Huang, Scott C. -H. Chang, Cheng-Shang Chen, Cheng-Yu Natl Tsing Hua Univ Inst Commun Engn Hsinchu 30013 Taiwan

In this letter, we consider the conflict resolution problem in a discrete-time multiple access channel. Our focus is the duration of achieving the first successful transmission, called the conflict resolution time. Assume that each device has a unique ID. Our proposed nonadaptive deterministic algorithms can guarantee deterministic upper bounds on the conflict resolution time even when the clocks of the devices in the channel are not synchronized. Furthermore, on average, our proposed algorithms achieve short conflict resolution time on par with existing randomized algorithms (e.g., independent fair coin flipping) in the literature.

关键词： Multiple access nonadaptive algorithms worst case analysis

来源：评论

学校读者我要写书评

暂无评论

An upper bound of the number of tests in pooling designs for the error-tolerant complex model

引用

OPTIMIZATION LETTERS 2008年第3期2卷 425-431页

作者： Chen, Hong-Bin Fu, Hung-Lin Hwang, Frank K. Natl Chiao Tung Univ Dept Appl Math Hsinchu 30050 Taiwan

Recently pooling designs have been used in screening experiments in molecular biology. In some applications, the property to be screened is defined on subsets of items, instead of on individual items. Such a model is usually referred to as the complex model. In this paper we give an upper bound of the number of tests required in a pooling design for the complex model (with given design parameters) where experimental errors are allowed.

关键词： Pooling designs nonadaptive algorithms Disjunct matrices

来源：评论

学校读者我要写书评

暂无评论

Optimal reconstruction of graphs under the additive model

引用

ALGORITHMICA 2000年第1期28卷 104-124页

作者： Grebinski, V Kucherov, G INRIA Lorraine LORIA F-54602 Villers Les Nancy France

We study the problem of reconstructing unknown graphs under the additive combinatorial search model. The main result concerns the reconstruction of bounded degree graphs, i.e., graphs with the degree of all vertices bounded by a constant d. We show that such graphs can be reconstructed in O(dn) nonadaptive queries, which matches the information-theoretic lower bound. The proof is based on the technique of separating matrices. A central result here is a new upper bound for a general class of separating matrices. As a particular case, we obtain a tight upper bound for the class of d-separating matrices, which settles an open question stated by Lindstrom in [20]. Finally, we consider several particular classes of graphs. We show how an optimal nonadaptive solution of O(n(2)/log n) queries for general graphs can be obtained. We also prove that trees with unbounded vertex degree can be reconstructed in a linear number of queries by a nonadaptive algorithm.

关键词： combinatorial search nonadaptive algorithms graph reconstruction coin weighing

来源：评论

学校读者我要写书评

暂无评论

Optimal reconstruction of graphs under the additive model 5th

Optimal reconstruction of graphs under the additive model

引用

5th European Symposium on algorithms (ESA 97)

作者： Grebinski, V Kucherov, G INRIA Lorraine LORIA F-54602 Villers Les Nancy France

ISBN: (纸本)3540633979

关键词： combinatorial search nonadaptive algorithms graph reconstruction coin weighing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：