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

Optimal bounds on finding fixed points of contraction mappings

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1742-1749页

作者： Chang, Ching-Lueh Lyuu, Yuh-Dauh Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 10764 Taiwan Natl Taiwan Univ Dept Finance Taipei 10764 Taiwan

The Banach fixed-point theorem states that a contraction mapping on a complete metric space has a unique fixed point. Given an oracle access to a finite metric space (M, d) and a contraction mapping f : M -> M on it, we show that the fixed point off can be found with an expected O(root vertical bar M vertical bar) oracle queries. We also show that every randomized algorithm for finding a fixed point must make an expected Omega(root vertical bar M vertical bar) oracle queries to (M, d) and f for some finite metric space (M, d) and some contraction mapping f : M -> M on it. As a generalization of the Banach fixed-point theorem, the Caristi-Kirk fixed-point theorem gives weaker conditions on (M. d) and f guaranteeing the existence of a fixed point off. We show that every randomized algorithm that finds a fixed point must make the expected Omega(vertical bar M vertical bar) oracle queries to (M. d) and f for some finite metric space (M, d) and some function f : M -> M satisfying the conditions of the Caristi-Kirk fixed-point theorem. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Contraction mapping principle Banach fixed-point theorem Caristi-Kirk fixed-point theorem query complexity

来源：评论

学校读者我要写书评

暂无评论

SPAN PROGRAMS ARE EQUIVALENT TO QUANTUM query ALGORITHMS

引用

SIAM JOURNAL ON COMPUTING 2014年第3期43卷 1206-1219页

作者： Reichardt, Ben W. Univ So Calif Los Angeles CA 90089 USA

Span programs form a linear-algebraic model of computation that is studied to prove classical lower bounds. Quantum query complexity is a coherent generalization for quantum algorithms of decision-tree complexity. It is characterized by a semidefinite program known as the general adversary bound. We connect these classical and quantum models by proving that for any boolean function, the optimal "witness size" of a span program equals the general adversary bound. Therefore, span program witness size and quantum query complexity are equivalent measures. In particular, quantum algorithms can be designed based on span programs.

关键词： quantum computing query complexity span program adversary method function composition

来源：评论

学校读者我要写书评

暂无评论

From Discrepancy to Majority

引用

ALGORITHMICA 2018年第4期80卷 1278-1297页

作者： Eppstein, David Hirschberg, Daniel S. Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA

We show how to select an item with the majority color from n two-colored items, given access to the items only through an oracle that returns the discrepancy of subsets of k items (the absolute value of the difference between the numbers of items with each color). We use queries, improving a previous method by De Marco and Kranakis that used queries. We also prove a lower bound of on the number of queries needed, both for discrepancy queries and to queries that return the partition of items into monochromatic subsets. This improves a lower bound of by De Marco and Kranakis.

关键词： Set discrepancy Majority Algorithms Lower bounds query complexity

来源：评论

学校读者我要写书评

暂无评论

Quantum Algorithms for Testing Properties of Distributions

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第6期57卷 3971-3981页

作者： Bravyi, Sergey Harrow, Aram W. Hassidim, Avinatan IBM Watson Res Ctr Yorktown Hts NY 10598 USA Univ Bristol Dept Math Bristol BS8 1TW Avon England MIT Cambridge MA 02139 USA

Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L(1)-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L(1)-distance parallel to p-q parallel to(1) can be estimated with a constant precision using only O(N(1/2)) queries in the quantum settings, whereas classical computers need Omega(N(1-o(1))) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N(1/3)). The classical query complexity of these problems is known to be Omega(N(1/2)).

关键词： Property testing sampling quantum information query complexity statistical distance

来源：评论

学校读者我要写书评

暂无评论

Quantum and Classical query Complexities of Local Search Are Polynomially Related

引用

ALGORITHMICA 2009年第3期55卷 557-575页

作者： Santha, Miklos Szegedy, Mario Univ Paris Sud CNRS LRI F-91405 Orsay France Rutgers State Univ Piscataway NJ 08854 USA

Let f be an integer valued function on a finite set V. We call an undirected graph G(V,E) a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) find a vertex xaV such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form "what is the value of f on x?" We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous (Ann. Probab. 11(2):403-413, [1983]) and Aaronson (SIAM J. Comput. 35(4):804-824, [2006]) and solves the main open problem in Aaronson (SIAM J. Comput. 35(4):804-824, [2006]).

关键词： Local search query complexity Quantum computing

来源：评论

学校读者我要写书评

暂无评论

On the Black-Box complexity of Sperner's Lemma

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 629-646页

作者： Friedl, Katalin Ivanyos, Gabor Santha, Miklos Verhoeven, Yves F. Budapest Univ Technol & Econ H-1521 Budapest Hungary Hungarian Acad Sci Comp & Automat Res Inst H-1518 Budapest Hungary Univ Paris 11 CNRS LRI F-91405 Orsay France Natl Univ Singapore Ctr Quantum Technol Singapore 117543 Singapore Univ Paris 11 LRI F-91405 Orsay France ENST F-75013 Paris France

We present several results on the complexity of various forms of Sperner's Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an O(root n) deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou's complexity class PPAD. This upper bound matches the Omega(root n) deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an Omega((4)root n) lower bound for its probabilistic, and an Omega((8)root n) lower bound for its quantum query complexity, showing that all these measures are polynomially related.

关键词： query complexity Sperner's lemma Deterministic algorithm Probabilistic and quantum lower bound

来源：评论

学校读者我要写书评

暂无评论

A New Minimax Theorem for Randomized Algorithms

引用

JOURNAL OF THE ACM 2023年第6期70卷 1-58页

作者： Ben-David, Shalev Blais, Eric Univ Waterloo 200 Univ Ave West Waterloo ON N2L 3G1 Canada

The celebrated minimax principle of Yao says that for any Boolean-valued function f with finite domain, there is a distribution mu over the domain of f such that computing f to error. against inputs from mu is just as hard as computing f to error. on worst-case inputs. Notably, however, the distribution mu depends on the target error level.: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution mu that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumann's minimax theorem or linear programming duality. First, we use Sion's minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as "forecasting algorithms" evaluated by a certain proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties-for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.

关键词： Minimax randomized computation quantum computation query complexity communication complexity polynomial degree complexity circuit complexity

来源：评论

学校读者我要写书评

暂无评论

Being a permutation is also orthogonal to one-wayness in quantum world: Impossibilities of quantum one-way permutations from one-wayness primitives

引用

THEORETICAL COMPUTER SCIENCE 2021年 855卷 16-42页

作者： Cao, Shujiao Xue, Rui Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Univ Acad Sci Sch Cyber Secur Beijing Peoples R China

In this paper, three impossible results for one-way permutations in the quantum world are obtained. The first one is the impossibility of fully black-box reduction from one-way permutations to one-way functions in a quantum setting. The two-oracle method is the main technique adopted in our proof that was originally proposed by Hsiao and Reyzin, and extended later to a quantum setting by Hosoyamada and Yamakawa. Informally this technique involves a pair of oracles, and in our proof, one oracle is chosen as a random function, and the other one is devised for breaking the security of quantum one-way permutation. We show, according to the first oracle, that there is an oracle-aided circuit that is a quantum-secure one-way function. However, we also show, according to the second oracle, that there is no one-way permutation relative to those oracles. It hence claims the impossibility in the quantum setting to construct one-way permutations from one-way functions (even if both input and output are classical). The rest two impossibilities are essential enhancements of the first impossibility: We successfully obtain that it is impossible, in the quantum world, to obtain one-way permutations in a black-box manner from injective adaptive one-way functions, and (respectively) even from injective adaptive trapdoor functions. In order to reach the latter two results, we manage to get over the obstacle of finding the inverse of random injective functions even given the partial invert oracle in the quantum setting. As a result, we get a quantum lower bound of inverting random injective functions in random case. That should be of independent interest in this paper, which might, to authors' knowledge, be the first quantum lower bound of inverting random injective functions given the partial invert oracle. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Quantum computing query complexity Black-box reduction Quantum one-way function One-way permutation

来源：评论

学校读者我要写书评

暂无评论

Playing Mastermind With Many Colors

引用

JOURNAL OF THE ACM 2016年第5期63卷 1–23页

作者： Doerr, Benjamin Doerr, Carola Spoehel, Reto Thomas, Henning Max Planck Inst Informat Saarbrucken Germany Univ Paris Diderot Paris France Swiss Fed Inst Technol Inst Theoret Comp Sci CH-8092 Zurich Switzerland Ecole Polytech UMR 7161 LIX 1 Rue Honore Estienne OrvesBatiment Alan Turing F-91120 Palaiseau France UPMC Univ Paris 06 Sorbonne Univ CNRS LIP6UMR 7606 4 Pl Jussieu F-75005 Paris France Bern Univ Appl Sci Engn & Informat Technol CH-3400 Burgdorf Switzerland

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k 0 a constant, is well understood, we concentrate on larger numbers of colors. For the most promin... 详细信息

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k <= n(1-epsilon), e > 0 a constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n, our results imply that Codebreaker can find the secret code with O(n log log n) guesses. This bound is valid also when only black answer pegs are used. It improves the O(n log n) bound first proven by Chvatal. We also show that if both black and white answer pegs are used, then the O(n log log n) bound holds for up to n(2) log log n colors. These bounds are almost tight, as the known lower bound of ohm(n) shows. Unlike for k <= n(1-epsilon), simply guessing at random until the secret code is determined is not sufficient. In fact, we show that an optimal nonadaptive strategy (deterministic or randomized) needs circle minus(n log n) guesses.

关键词： Combinatorial games Mastermind query complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Quantum certificate complexity

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2008年第3期74卷 313-322页

作者： Aaronson, Scott Inst Adv Study Princeton NJ 08540 USA

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation Ro(f) = O(Q(2)(f)(2)Q(0)(f)log n) for total f, where R-0, Q(2), and Q(0) are zero-error randomized, bounded-error quantum, and zero-error quantum query complexities respectively. Finally we give asymptotic gaps between the measures, including a total f for which C(f) is superquadratic in QC(f), and a symmetric partial f for which QC(f) = O(1) Yet Q(2)(f) = Omega(n/log n). (c) 2007 Elsevier Inc. All rights reserved.

关键词： quantum computing query complexity black box decision tree block sensitivity adversary method merlin-arthur boolean function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：