Applications of Ramsey's theorem to decision tree complexity

Combinatorial techniques for extending lower bound results for decision trees to general types of queries are presented. Problems that are defined by simple ...