Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-086-87
Monotone Bipartite Graph Properties are Evasive
Authors: Yao, Andrew Chi-Chih
Date:April 1987
Pages:8
Download Formats: [PDF]
Abstract:
A Boolean function P from {0,1}t into {0,1} is said to be evasive, if every decision tree algorithm for evaluating P must examine at least t arguments in the worst case. It was known that any nontrivial monotone bipartite graph property on vertex set V x W must be evasive, when |V| x |W| is a power of a prime number. In this paper, we prove that every nontrivial monotone bipartite graph property is evasive.