In this paper on "The Polynomial Hierarchy, Random Oracles, and Boolean Circuits", Fact (3.2) states that it is impossible for a polylogarithmic depth decision tree to compute the Tribes-DNF much better than randomly guessing.

There is no proof given, and I'm unable to reconstruct the solution from the hints in the text. I'm also unable to find many references in general for proving lower bounds on approximate decision trees. Any ideas on how to approach this problem?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.