Lower bounds on probabilistic linear decision trees

Research output: Contribution to journalArticlepeer-review


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
Issue numberC
StatePublished - 1985
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this