๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Average-Case Lower Bounds for Noisy Boolean Decision Trees

โœ Scribed by Evans, William; Pippenger, Nicholas

Book ID
118178204
Publisher
Society for Industrial and Applied Mathematics
Year
1998
Tongue
English
Weight
307 KB
Volume
28
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Lower bounds for algebraic decision tree
Lower bounds for algebraic decision trees
โœ J Michael Steele; Andrew C Yao ๐Ÿ“‚ Article ๐Ÿ“… 1982 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 445 KB
Entropy lower bounds for quantum decisio
Entropy lower bounds for quantum decision tree complexity
โœ Yaoyun Shi ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 70 KB

We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard decision tree computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log n) bits. Let E(f ) be the Shanno

Upper and lower bounds for the average-c
Upper and lower bounds for the average-case complexity of path-search
โœ Pippenger, Nicholas ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 125 KB ๐Ÿ‘ 1 views

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting ent