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

Optimal direct sum results for deterministic and randomized decision tree complexity

INFORMATION PROCESSING LETTERS 2010年第20期110卷 893-897页

作者： Jain, Rahul Klauck, Hartmut Santha, Miklos Natl Univ Singapore Ctr Quantum Technol Singapore 117548 Singapore Natl Univ Singapore Dept Comp Sci Singapore 117548 Singapore Nanyang Technol Univ Ctr Quantum Technol NUS Singapore Singapore Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore Univ Paris 11 CNRS LRI F-91405 Orsay France Natl Univ Singapore Ctr Quantum Technol Singapore 117548 Singapore

A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Computational complexity Direct sum decision tree complexity

来源：评论

学校读者我要写书评

暂无评论

complexity measures and decision tree complexity: a survey

引用

THEORETICAL COMPUTER SCIENCE 2002年第1期288卷 21-43页

作者： Buhrman, H de Wolf, R CWI NL-1098 SJ Amsterdam Netherlands Univ Amsterdam ILLC NL-1018 TV Amsterdam Netherlands

We discuss several complexity measures for Boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of Boolean functions on deterministic, randomized, and quantum computers. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： decision tree complexity complexity measures for Boolean functions randomized computing quantum computing

来源：评论

学校读者我要写书评

暂无评论

An Improved Lower Bound for the Randomized decision tree complexity of Recursive Majority 1

引用

40th International Colloquium on Automata, Languages and Programming (ICALP)

作者： Leonardos, Nikos Univ Athens Dept Informat & Telecommun Athens Greece

ISBN: (数字)9783642392061

ISBN: (纸本)9783642392061

We prove that the randomized decision tree complexity of the recursive majority- of- three is Omega(2.55(d)), where d is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their 1986 paper on the complexity of evaluating game trees. Previous work includes an Omega (7/3)(d)) lower bound, published in 2003 by Jayram, Kumar, and Sivakumar. Their proof used a top down induction and tools from information theory. In 2011, Magniez, Nayak, Santha, and Xiao, improved the lower bound to Omega((5/2)(d)) and the upper bound to O(2.64946(d)).

关键词： Boolean functions randomized computation decision tree complexity query complexity lower bounds generalized costs

来源：评论

学校读者我要写书评

暂无评论

New bounds for energy complexity of Boolean functions

引用

THEORETICAL COMPUTER SCIENCE 2020年 845卷 59-75页

作者： Dinesh, Krishnamoorthy Otiv, Samir Sarma, Jayalal Indian Inst Technol Madras Chennai Tamil Nadu India Maximl Labs Vatakara India

For a Boolean function f:{0, 1}(n) ->{0, 1} computed by a Boolean circuit Cover a finite basis B, the energy complexityof C(denoted by ECB(C)) is the maximum over all inputs {0, 1}(n) of the number gates of the circuit C(excluding the inputs) that output a one. Energy complexity of a Boolean function over a finite basis Bdenoted by ECB(f) (def)= min(C) ECB(C) where Cis a Boolean circuit over Bcomputing f. We study the case when B={boolean AND(2), boolean OR(2), (sic)}, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most 3n(1 + is an element of(n)) for a small is an element of(n)(which we observe is improvable to 3n - 1). We show several new results and connections between energy complexity and other wellstudied parameters of Boolean functions. For all Boolean functions f, EC(f) <= O(DT(f)(3)) where DT(f) is the optimal decision tree depth of f. We define a parameter positive sensitivity(denoted by psens), a quantity that is smaller than sensitivity (Cook et al. 1986, [3]) and defined in a similar way, and show that for any Boolean circuit Ccomputing a Boolean function f, EC(C) >= psens(f)/3. For a monotone function f, we show that EC(f) = Omega(KW+ (f)) where KW+ (f) is the cost of monotone Karchmer-Wigderson game of f. Restricting the above notion of energy complexity to Boolean formulas, we show EC(F) = Omega(root L(F)-Depth(F)) where L(F) is the size and Depth(F) is the depth of a formula F. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Energy complexity Boolean circuits decision tree complexity Sensitivity Karchmer-Wigderson games Formula size

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Relativized collapsing between BPP and PH under stringent oracle access

引用

INFORMATION PROCESSING LETTERS 2004年第3期90卷 147-154页

作者： Cai, JY Watanabe, O Tokyo Inst Technol Dept Math & Comp Sci Tokyo 1528552 Japan Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

We propose a new model of stringent oracle access defined for a general complexity class. For example, when comparing the power of two machine models relative to some oracle set X, we restrict that machines of both types ask queries from the same segment of the set X. In particular, for investigating polynomial-time (or polynomial-size) computability, we propose polynomial stringency, bounding query length to any fixed polynomial of input length. Under such stringent oracle access, we show an oracle G such that BPPG = PHG. (C) 2004 Elsevier B.V. All rights reserved.

关键词： computational complexity stringent relativization polynomial hierarchy switching lemma decision tree complexity bounded error probabilistic polynomial time

来源：评论

学校读者我要写书评

暂无评论

A LOWER BOUND FOR THE complexity OF MONOTONE GRAPH PROPERTIES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第1期27卷 257-265页

作者： Scheidweiler, Robert Triesch, Eberhard Rhein Westfal TH Aachen Lehrstuhl Math 2 D-52062 Aachen Germany

More than 30 years ago, Karp conjectured that all nontrivial monotone graph properties are evasive, i.e., have decision tree complexity ((n)(2)), where n is the number of vertices. It was proved in 1984 by Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297-306] if n is a prime power by a topological approach. Using their method, we prove a lower bound of 1/3 n(2) - o(n(2)) for general n.

关键词： evasiveness decision tree complexity graph properties

来源：评论

学校读者我要写书评

暂无评论

Evasiveness of subgraph containment and related properties

引用

SIAM JOURNAL ON COMPUTING 2002年第3期31卷 866-875页

作者： Chakrabarti, A Khot, S Shi, YY Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

We prove new results on evasiveness of monotone graph properties by extending the techniques of Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297-306]. For the property of containing a subgraph isomorphic to a fixed graph, and a fairly large class of related n-vertex graph properties, we show evasiveness for an arithmetic progression of values of n. This implies a 1/2n(2)-O (n) lower bound on the decision tree complexity of these properties. We prove that properties that are preserved under taking graph minors are evasive for all sufficiently large n. This greatly generalizes a theorem due to Best, van Emde Boas, and Lenstra [A Sharpened Version of the Aanderaa-Rosenberg Conjecture, Report ZW 30/74, Mathematisch Centrum, Amsterdam, The Netherlands, 1974] which states that planarity is evasive. We prove a similar result for bipartite subgraph containment.

关键词： decision tree complexity monotone graph properties evasiveness topological method graph property testing

来源：评论

学校读者我要写书评

暂无评论

An improved lower bound on the sensitivity complexity of graph properties

引用

THEORETICAL COMPUTER SCIENCE 2011年第29期412卷 3524-3529页

作者： Sun, Xiaoming Tsinghua Univ Ctr Adv Study Beijing 100084 Peoples R China Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

Turan (1984) [11] initiated the study of the sensitivity complexity of graph properties. He conjectured that for any non-trivial graph properties on n vertices, the sensitivity complexity is at least n-1. He proved an left perpendicularn/4right perpendicular lower bound for sensitivity in his paper: Turan (1984) [11]. Wegener (1985) [12] proved this conjecture for all monotone graph properties. In this paper we improve Turan's lower bound to 6/17n (approximate to 0.35n). We hope that this will shed some light on the proof of Turan's conjecture. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Computational complexity decision tree complexity Sensitivity complexity Graph property

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：