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

Any monotone property of 3-uniform hypergraphs is weakly evasive

THEORETICAL COMPUTER SCIENCE 2015年 588卷 16-23页

作者： Kulkarni, Raghav Qiao, Youming Sun, Xiaoming Natl Univ Singapore Ctr Quantum Technol Singapore 117548 Singapore Univ Technol Sydney Ctr Quantum Computat & Intelligent Syst Sydney NSW 2007 Australia Chinese Acad Sci Inst Comp Technol CAS Key Lab Network Data Sci & Technol Beijing 100190 Peoples R China

For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuillemin [11] show that any non-constant monotone property P : {0, 1}((n/2)) -> {0, 1} of n-vertex graphs has D(P) = Omega (n(2)). We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P : {0, 1}((n/3)) -> {0, 1} of n-vertex 3-uniform hypergraphs has D (P) = Omega (n(3)). Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant [6]. Interestingly, our proof makes use of Vinogradov's Theorem (weak Goldbach Conjecture), inspired by its recent use by Babai et al. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Decision tree complexity Hypergraph properties Evasiveness query complexity Group actions

来源：评论

学校读者我要写书评

暂无评论

Claw finding algorithms using quantum walk

引用

THEORETICAL COMPUTER SCIENCE 2009年第50期410卷 5285-5297页

作者： Tani, Seiichiro NTT Corp NTT Commun Sci Labs Kanagawa 2430198 Japan Japan Sci & Technol Agcy Quantum Computat & Informat Project Bunkyo Ku Tokyo 1130033 Japan

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f and g, with domain sizes N and M(N <= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. it can also be generalized to find a claw of k functions for any constant integer k > 1, where the domain sizes of the functions may be different. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Quantum computing query complexity Oracle Computation Quantum walk

来源：评论

学校读者我要写书评

暂无评论

QUANTUM query ALGORITHMS ARE COMPLETELY BOUNDED FORMS

引用

SIAM JOURNAL ON COMPUTING 2019年第3期48卷 903-925页

作者： Arunachalam, Srinivasan Briet, Jop Palazuelos, Carlos QuSoft CWI Amsterdam Netherlands Univ Amsterdam Amsterdam Netherlands CWI NL-1098 XG Amsterdam Netherlands Univ Complutense Madrid Inst Ciencias Matemat Fac CC Matemat Madrid Spain

We prove a characterization of t-query quantum algorithms in terms of the unit ball of a space of degree-(2t) polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. ["Polynomials, Quantum query complexity, and Grothendieck's Inequality," in Proceedings of the 31st Conference on Computational complexity, CCC 2016, Schloss Dagstuh, 2016, pp. 25:1-25:19]. Our proof is based on a fundamental result of Christensen and Sinclair [J. Funct. Anal., 72 (1987), pp. 151-181] that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.

关键词： quantum algorithms query complexity multilinear forms C*-algebras operator space theory polynomial method

来源：评论

学校读者我要写书评

暂无评论

On the complexity of searching for a maximum of a function on a quantum computer

引用

QUANTUM INFORMATION PROCESSING 2006年第1期5卷 31-41页

作者： Gocwin, Maciej AGH Univ Sci & Technol Dept Appl Math PL-30059 Krakow Poland

We deal with the problem of finding a maximum of a function from the Holder class on a quantum computer We show matching lower and upper bounds oil the complexity of this problem. We prove upper bounds by constructing an alogorithm that uses a pre-exisiting quantum algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding the logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.

关键词： numerical optimization optimal algorithm quantum computing query complexity

来源：评论

学校读者我要写书评

暂无评论

Mastermind with a linear number of queries

引用

COMBINATORICS PROBABILITY AND COMPUTING 2024年第2期33卷 143-156页

作者： Martinsson, Anders Su, Pascal Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

Since the 1960s Mastermind has been studied for the combinatorial and information-theoretical interest the game has to offer. Many results have been discovered starting with Erdos and Renyi determining the optimal number of queries needed for two colours. For $k$ colours and $n$ positions, Chvatal found asymptotically optimal bounds when $k \le n<^>{1-\varepsilon }$. Following a sequence of gradual improvements for $k\geq n$ colours, the central open question is to resolve the gap between $\Omega (n)$ and $\mathcal{O}(n\log \log n)$ for $k=n$. In this paper, we resolve this gap by presenting the first algorithm for solving $k=n$ Mastermind with a linear number of queries. As a consequence, we are able to determine the query complexity of Mastermind for any parameters $k$ and $n$.

关键词： Mastermind coin-weighing information theory combinatorial games query complexity

来源：评论

学校读者我要写书评

暂无评论

The (Im)Possibility on Constructing Verifiable Random Functions

引用

COMPUTER JOURNAL 2022年第7期65卷 1826-1845页

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

In this paper, we further explore the properties of the verifiable random functions in both a black-box and a non-black-box manner. The results are mainly following two parts: Black-Box Barrier: It is set up for an impossibility result of black-box reduction from verifiable random functions to injective one-way functions and indistinguishability obfuscators, where the verifiable random functions are suggested to be domain-invariant (i.e. the support of the distribution of keys and the domain of the evaluation space are independent of the underlying building blocks). Our result illustrates how the non-domain-invariant constructions circumvent the black-box barriers for constructing verifiable random functions and sheds light on why it is so difficult to give a domain-invariant instantiation. Non-Black-Box Construction: On the other hand, the verifiable unpredictable functions are constructed from a given primitive by a non-black-box technique called the hitting-set generator. To show it's a somewhat useful technique for constructing the verifiable unpredictable functions, we further derive a limitation of the black-box barrier by proving the barrier still holds between the given primitive and verifiable unpredictable functions. Our results not only analyse the properties of verifiable random functions theoretically, but also reveal the limitation of indistinguishability obfuscators in a black-box manner, and show the advantages by adopting non-black-box techniques.

关键词： Verifiable Random Functions Indistinguishability Obfuscator Black-Box Reduction Two-Oracle Technique query complexity

来源：评论

学校读者我要写书评

暂无评论

Distributed Methods for Computing Approximate Equilibria

引用

ALGORITHMICA 2019年第3期81卷 1205-1231页

作者： Czumaj, Artur Deligkas, Argyrios Fasoulakis, Michail Fearnley, John Jurdzinski, Marcin Savani, Rahul Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Warwick DIMAP Coventry W Midlands England Technion Fac Ind Engn & Management Haifa Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Fdn Res & Technol Hellas ICS FORTH Inst Comp Sci Iraklion Greece

We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players' payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computing approximate well supported Nash equilibria (WSNE) that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case of approximate Nash equilibria, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makes O(nlogn) payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.

关键词： Approximate Nash equilibria Bimatrix games Communication complexity query complexity

来源：评论

学校读者我要写书评

暂无评论

The quantum black-box complexity of majority

引用

ALGORITHMICA 2002年第4期34卷 480-501页

作者： Hayes, TP Kutin, S van Melkebeek, D Univ Chicago Dept Math Chicago IL 60637 USA Univ Chicago Dept Comp Sci Chicago IL 60637 USA Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

We describe a quantum black-box network computing the majority of N bits with zero-sided error the correct answer with probability epsilon using only 2/3 N + O (rootN log(epsilon(-1) log N)) queries: the algorithm returns at least 1 - epsilon, and "I don't know" otherwise. Our algorithm is given as a randomized "XOR decision tree" for which the number of queries on any input is strongly concentrated around a value of at most 2/3 N. We provide a nearly matching lower bound of 2/3 N - O(rootN) on the expected number of queries on a worst-case input in the randomized XOR decision tree model with zero-sided error o(1). Any classical randomized decision tree computing the majority on N bits with zero-sided error 1/2 has cost N.

关键词： majority function quantum computing query complexity Las Vegas algorithms

来源：评论

学校读者我要写书评

暂无评论

Parity decision tree in classical-quantum separations for certain classes of Boolean functions

引用

QUANTUM INFORMATION PROCESSING 2021年第6期20卷 1-25页

作者： Mukherjee, Chandra Sekhar Maitra, Subhamoy Indian Stat Inst Kolkata India

In this paper, we study the separation between the deterministic (classical) query complexity (D) and the exact quantum query complexity (Q(E)) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on n variables as the ones with minimum deterministic query complexity D(f). We observe that for each n, there exists a non-separable class of QF functions such that D(f) = Q(E) (f). Further, we show that for some values of n, all the QF functions are non-separable. Then, we present QF functions for certain other values of n where separation can be demonstrated, in particular, Q(E) (f) = D(f) - 1. In a related effort, we also study theMaiorana-McFarland (MM)-type Bent functions. We show that while for any MM Bent function f on n variables D(f) = n, separation can be achieved as n/2 <= Q(E) (f) <= inverted right perpendicular3n/4inverted left perpendicular. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.

关键词： Boolean functions Bent functions Classical-quantum separation Parity decision tree query complexity query friendly functions

来源：评论

学校读者我要写书评

暂无评论

Learning Equilibria of Games via Payoff Queries

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2015年第1期16卷 1305-1344页

作者： Fearnley, John Gairing, Martin Goldberg, Paul W. Savani, Rahul Univ Liverpool Ashton BldgAshton St Liverpool L69 3BX Merseyside England Univ Oxford Oxford OX1 2JD England

A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for exact equilibria of bimatrix and graphical games. We then study the query complexity of approximate equilibria in bimatrix games. Finally, we study the query complexity of exact equilibria in symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.

关键词： query complexity bimatrix game congestion game equilibrium computation approximate Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：