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

HARDNESS OF CONTINUOUS LOCAL SEARCH: query complexity AND CRYPTOGRAPHIC LOWER BOUNDS

SIAM JOURNAL ON COMPUTING 2020年第6期49卷 1128-1172页

作者： Hubacek, Pavel Yogev, Eylon Charles Univ Prague Prague Czech Republic Boston Univ Boston MA 02215 USA Tel Aviv Univ IL-6997801 Tel Aviv Israel

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g., via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts, the optimization problem is defined by a continuous function which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class CLS [C. Daskalakis and C. H. Papadimitriou, Proceedings of SODA'11, 2011], which is contained in the intersection of PLS and PPAD, two important subclasses of TFNP (the class of NP search problems with a guaranteed solution). In this work, we show the first hardness results for CLS (the smallest nontrivial class among the currently defined subclasses of TFNP). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions. Our results demonstrate a strong conceptual barrier precluding design of efficient algorithms for solving local search problems even over continuous domains. As our main technical contribution we introduce a new total search problem which we call END-OF-METERED-LINE. The special structure of END-OF-METERED-LINE enables us to (1) show that it is contained in CLS, (2) prove hardness for it in both the black-box and the white-box setting, and (3) extend to CLS a variety of results previously known only for PPAD.

关键词： CLS continuous local search cryptographic hardness PLS PPAD query complexity TFNP

来源：评论

学校读者我要写书评

暂无评论

Quadratically Tight Relations for Randomized query complexity

引用

THEORY OF COMPUTING SYSTEMS 2020年第1期64卷 101-119页

作者： Jain, Rahul Klauck, Hartmut Kundu, Srijita Lee, Troy Santha, Miklos Sanyal, Swagato Vihrovs, Jevgenijs Natl Univ Singapore Ctr Quantum Technol Block S153 Sci Dr 2 Singapore 117543 Singapore MajuLab UMI 3654 Singapore Singapore Nanyang Technol Univ SPMS 21 Nanyang Link Singapore 637371 Singapore Univ Paris Diderot IRIF CNRS F-75205 Paris France Univ Latvia Fac Comp Ctr Quantum Comp Sci Raina 19 LV-1586 Riga Latvia

In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) = R0(f) = C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) = R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 = R(f). We then prove that EC(f) = C(f) = EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional certificate complexity FC(f) as follows: FC(f) = EC(f) = O(FC(f)3/2). This also connects to an open question by Aaronson whether FC(f) is a quadratically tight bound for R0(f), as EC(f) is in fact a relaxation of FC(f). In the second part of the work, we investigate whether the corruption bound corr (f) quadratically approximates R(f). By Yao's theorem, it is enough to prove that the square of the corruption bound upper bounds the distributed query complexity D mu (f) for all input distributions mu. Here, we show that this statement holds for input distributions in which the various bits of the input are distributed independently. This is a natural and interesting subclass of distributions, and is also in the spirit of the input distributions studied in communication complexity in which the inputs to the two communicating parties are statistically independent. Our result also improves upon a result of Harsha et al. (2016), who proved a similar weaker statement. We also note that a similar statement in the communication complexity is open.

关键词： query complexity Randomized algorithms Certificate complexity Fractional block sensitivity Corruption bound

来源：评论

学校读者我要写书评

暂无评论

Unbounded-error quantum query complexity

引用

THEORETICAL COMPUTER SCIENCE 2011年第35期412卷 4619-4628页

作者： Montanaro, Ashley Nishimura, Harumichi Raymond, Rudy IBM Res Tokyo Yamato 2428502 Japan Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB2 1TN England Osaka Prefecture Univ Sch Sci Osaka Japan

This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the "black-box" approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve-Wigderson [STOC'98] is optimal even in the unbounded-error setting. We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p 1/2)), where q is the number of queries made and p > 1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Theta(log n) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.

关键词： Quantum computing query complexity Communication complexity

来源：评论

学校读者我要写书评

暂无评论

SEPARATION BETWEEN DETERMINISTIC AND RANDOMIZED query complexity

引用

SIAM JOURNAL ON COMPUTING 2018年第4期47卷 1644-1666页

作者： Mukhopadhyay, Sagnik Radhakrishnan, Jaykumar Sanyal, Swagato KTH Royal Inst Technol Stockholm Sweden Tata Inst Fundamental Res Bombay Maharashtra India IIT Kharagpur Dept Comp Sci & Engn Kharagpur W Bengal India

Saks and Wigderson 27th FOGS, IEEE Computer Society, as Alamitos, CA, 1986, pp. 29-38] conjectured that R-0(f) = Omega (D(f)(0.753...)) for all Boolean functions f, here R-0 denotes the randomized complexity and D denotes 10 determinist is query CCATI p1exit;,yr. We,show t hat for the pointer function GPW(rxs) defined by Goos. Pitassi, arid Watson [in Proceedings of the 56th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077-1088] the following hold: s) s) and (b) R-1(GPW(rxs)) = Irs), cyhere R1 denotes the randomized one-sided error query complexity. These results imply that (i) R-0(GPW(s2xs)) = O(D(GPW(s2xs))2/3) t hereby refuting the;conjecture of Saks and Wigdorson, and (ii) R-1 (GPW(sxs))- O(R-0(GPW(sxs))(2/3)), thereby providing a polynomial separation between the randomized zero -error and one-sided error query complexity measures.

关键词： deterministic decision tree randomized decision tree query complexity models of computation

来源：评论

学校读者我要写书评

暂无评论

A lower bound on the quantum query complexity of read-once functions

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2004年第2期69卷 244-258页

作者： Barnum, H Saks, M Los Alamos Natl Lab Los Alamos NM 87545 USA Rutgers State Univ Dept Math Hill Ctr New Brunswick NJ 08903 USA DIMACS Princeton NJ USA

We establish a lower bound of Omega(rootn) on the bounded-error quantum query complexity of read-once Boolean functions. The result is proved via an inductive argument, together with an extension of a lower bound method of Ambainis. Ambainis' method involves viewing a quantum computation as a mapping from inputs to quantum states (unit vectors in a complex inner-product space) which changes as the computation proceeds. Initially the mapping is constant (the state is independent of the input). If the computation evalutes the function f then at the end of the computation the two states associated with any f-distinguished pair of inputs (having different f values) are nearly orthogonal. Thus the inner product of their associated states must have changed from 1 to nearly 0. For any set off-distinguished pairs of inputs, the sum of the inner products of the corresponding pairs of states must decrease significantly during the computation, By deriving an upper bound on the decrease in such a sum, during a single step, for a carefully selected set of input pairs, one can obtain a lower bound on the number of steps. We extend Ambainis' bound by considering general weighted sums off-distinguished pairs. We then prove our result for read-once functions by induction on the number of variables, where the induction step involves a careful choice of weights depending on f to optimize the lower bound attained. (C) 2004 Elsevier Inc. All rights reserved.

关键词： quantum query complexity quantum computation query complexity decision tree complexity readonce functions lower bounds

来源：评论

学校读者我要写书评

暂无评论

The query complexity of a permutation-based variant of Mastermind

引用

DISCRETE APPLIED MATHEMATICS 2019年 260卷 28-50页

作者： Afshani, Peyman Agrawal, Manindra Doerr, Benjamin Doerr, Carola Larsen, Kasper Green Mehlhorn, Kurt Aarhus Univ Dept Comp Sci Aarhus Denmark Indian Inst Technol Kanpur Kanpur Uttar Pradesh India Ecole Polytech CNRS Lab Informat LIX Palaiseau France Sorbonne Univ CNRS LIP6 Paris France Max Planck Inst Informat Saarbrucken Germany

We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair (z, pi) which consists of a binary string z is an element of {0, 1}(n) and a permutation pi of [n]. The secret must be unveiled by asking queries of the form x is an element of {0, 1}(n). For each such query, we are returned the score f(z,pi)(X) := max{i is an element of [0..n] vertical bar for all j <= i : z(pi(j)) = x(pi(j))};i.e., the score of x is the length of the longest common prefix of x and z with respect to the order imposed by pi. The goal is to minimize the number of queries needed to identify (z, pi). This problem originates from the study of black-box optimization heuristics, where it is known as the LEADINGONES problem. In this work, we prove matching upper and lower bounds for the deterministic and randomized query complexity of this game, which are Theta(n log n) and Theta(n log log n), respectively. (C) 2019 Elsevier B.V. All rights reserved.

关键词： query complexity Hidden permutation Black-box complexity LEADINGONES

来源：评论

学校读者我要写书评

暂无评论

Optimal Composition Theorem for Randomized query complexity

引用

THEORY OF COMPUTING 2023年第1期19卷 1-35页

作者： Gavinsky, Dmytro Lee, Troy Santha, Miklos Sanyal, Swagato Czech Acad Sci Inst Math Zitna 25 Prague 115 67 Czech Republic Univ Technol Sydney Ctr Quantum Software & Informat Ultimo Australia Univ Paris Cite CNRS IRIF F-75013 Paris France Natl Univ Singapore CQT Singapore Singapore IIT Kharagpur Dept Comp Sci & Engn Kharagpur India

For any set S, any relation F subset of {0, 1}(n) x S and any partial Boolean function, defined on a subset of {0, 1}(m), we show that R-1/3 (f o g(n)) is an element of Omega (R-4/9(f) center dot root R-1/3(g)), where R-epsilon(center dot) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g(n) subset of ({0, 1}(m))(n) x S denotes the composition of 5 with = instances of g. This result is new even in the special case when S = {0, 1} and g is a total function. We show that the new composition theorem is optimal for the general case of relations: A relation f(0) and a partial Boolean function g(0) are constructed, such that R-4/9 (f(0)) is an element of Theta(root n), R-1/3(g(0)) is an element of Theta (n) and R-1/3(f(0) o g(0)(n)) is an element of Theta (n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by chi(center dot). Its investigation shows that (chi) over bar (g) is an element of Omega(R-1/3(g)) for any partial Boolean function g and (R-1/3(f o g(n)) is an element of Omega(R-4/9(f) center dot (chi) over bar (g)) for any relation f, which readily implies the composition statement. It is further shown that (chi) over bar (g) is always at least as large as the sabotage complexity of g (introduced by Ben-David and Kothari in 2016).

关键词： query complexity randomized decision tree composed function lower bound

来源：评论

学校读者我要写书评

暂无评论

The quantum query complexity of the hidden subgroup problem is polynomial

引用

INFORMATION PROCESSING LETTERS 2004年第1期91卷 43-48页

作者： Ettinger, M Hoyer, P Knill, E Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada Los Alamos Natl Lab Los Alamos NM 87545 USA

We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log I G 1) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers. Published by Elsevier B.V.

关键词： algorithms quantum computation hidden subgroups query complexity

来源：评论

学校读者我要写书评

暂无评论

IMPROVED DIRECT PRODUCT THEOREMS FOR RANDOMIZED query complexity

引用

COMPUTATIONAL complexity 2012年第2期21卷 197-244页

作者： Drucker, Andrew MIT Cambridge MA 02139 USA

The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty in computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1-epsilon in computing the Boolean function f on input distribution mu, then for alpha <= 1, every alpha epsilon Tk-query algorithm has success probability at most (2(alpha epsilon)(1-epsilon))(k) in computing the k-fold direct product f(circle times k) correctly on k independent inputs from mu. In light of examples due to Shaltiel, this statement gives an essentially optimal trade-off between the query bound and the error probability. Using this DPT, we show that for an absolute constant alpha > 0, the worst-case success probability of any alpha R-2(f) k-query randomized algorithm for f(circle dot k) falls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f(circle times k). Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.

关键词： Direct product theorems query complexity decision trees average-case complexity hardness amplification

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL SEPARATION OF RANDOMIZED AND QUANTUM query complexity

引用

SIAM JOURNAL ON COMPUTING 2023年第2期52卷 525-567页

作者： Sherstov, Alexander A. Storozhenko, Andrey A. Wu, Pei Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Inst Adv Study Princeton NJ 08540 USA

We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order l >= 1 sum to at most c(l) root((d)(l)) (1 + log n)(l-1), where n is the number of variables, d is the tree depth, and c > 0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. The bounds prior to our work degraded rapidly with l, becoming trivial already at l = root d. As an application, we obtain, for every integer k >= 1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k and randomized query complexity (Omega) over tilde (n(1) (1)(2k)). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [SIAM J. Comput., 47 (2018), pp. 982-1038] and Bravyi et al. [Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: O(1) versus Omega (n(2/3-epsilon)) for any epsilon > 0 [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. As another application, we obtain an essentially optimal separation of O(log n) versus Omega (n(1-epsilon)) for bounded-error quantum versus randomized communication complexity for any epsilon > 0. The best previous separation was polynomially weaker: O(log n) versus Omega(n(2/3-epsilon)) (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]).

关键词： quantum-classical separations query complexity communication complexity forrelation Fourier analysis of Boolean functions Fourier weight of decision trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：