Lower bounds on probabilistic linear decision trees

Research output: Contribution to journalArticlepeer-review

Abstract

The power of probabilistic linear decision trees is examined. It is shown that the standard arguments used to prove lower bounds on deterministic linear decision trees apply to probabilistic linear decision trees as well. Examples are next given of problems which randomization helps solving.

Original languageEnglish (US)
Pages (from-to)69-82
Number of pages14
JournalTheoretical Computer Science
Volume38
Issue numberC
DOIs
StatePublished - 1985
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Lower bounds on probabilistic linear decision trees'. Together they form a unique fingerprint.

Cite this