Randomization and the computational power of analytic and algebraic decision trees
type: Item
instance of: scholarly article
title: Randomization and the computational power of analytic and algebraic decision trees
zbMATH Open document ID: 0895.68050
DOI: 10.1007/BF01270388
author: Marek Karpinski
author: Roman Smolensky
author: Dima Grigoriev
published in: Computational Complexity
publication date: 1998-05-13T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 1151787
zbMATH Keywords: reduction technique
zbMATH Keywords: Boolean circuit
MaRDI profile type: Publication
cites work: Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
cites work: On randomized semi-algebraic test complexity
cites work: Q5732805
cites work: Q3772828
cites work: Decision trees
cites work: Q4228517
cites work: Q4252710
cites work: An exponential lower bound on the size of algebraic decision trees for MAX
cites work: Solving systems of polynomial inequalities in subexponential time
cites work: Complexity lower bounds for computation trees with elementary transcendental function gates
cites work: Q3957943
cites work: Learning Decision Trees Using the Fourier Spectrum
cites work: The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
cites work: Simulating probabilistic by deterministic algebraic computation trees
cites work: A note on Rabin's width of a complete proof
cites work: Proving simultaneous positivity of linear forms
cites work: Q5807665
cites work: A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests
cites work: NP is as easy as detecting unique solutions
cites work: Q4230349
cites work: Decision tree complexity and Betti numbers
description: scientific article; zbMATH DE number 1151787