Randomization and the computational power of analytic and algebraic decision trees
Authors:
- Dima GrigorievDGDima Grigoriev
- Marek KarpinskiMKMarek Karpinski
- Roman SmolenskyRSRoman Smolensky
- 1 December 1996
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 6 (4) , 376-388
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- A note on Rabin's width of a complete proofcomputational complexity, 1994
- On Randomized Semi-algebraic Test ComplexityJournal of Complexity, 1993
- Decision trees1993
- Linear decision trees1992
- Learning decision trees using the Fourier spectrum1991
- Solving systems of polynomial inequalities in subexponential timeJournal of Symbolic Computation, 1988
- Simulating probabilistic by deterministic algebraic computation treesTheoretical Computer Science, 1985
- The complexity of problems on probabilistic, nondeterministic, and alternating decision treesJournal of the ACM, 1985
- Lower bounds for algebraic computation trees1983
- Lower bounds for problems defined by polynomial inequalitiesLecture Notes in Computer Science, 1981