Applications of Ramsey's theorem to decision tree complexity

DOI10.1145/4221.4259zbMath0633.68030OpenAlexW2063243181MaRDI QIDQ3771610

Udi Manber, Shlomo Moran, Marc Snir

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/4221.4259

zbMATH Keywords

computational complexitydecision treesRamsey's theoremprobabilistic computationelement uniqueness problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decision theory (91B06) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Selection problems via \(m\)-ary queries ⋮ Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ A probabilistic distributed algorithm for set intersection and its analysis ⋮ The decision-tree complexity of element distinctness ⋮ Decision trees: Old and new results.

This page was built for publication: Applications of Ramsey's theorem to decision tree complexity