Randomization and the computational power of analytic and algebraic decision trees

DOI10.1007/BF01270388zbMath0895.68050MaRDI QIDQ1386179

Marek Karpinski, Roman Smolensky, Dima Yu. Grigoriev

Publication date: 13 May 1998

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

reduction techniqueBoolean circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Topological complexity of zero finding with algebraic operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP is as easy as detecting unique solutions
• Solving systems of polynomial inequalities in subexponential time
• On randomized semi-algebraic test complexity
• An exponential lower bound on the size of algebraic decision trees for MAX
• A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests
• A note on Rabin's width of a complete proof
• Complexity lower bounds for computation trees with elementary transcendental function gates
• Simulating probabilistic by deterministic algebraic computation trees
• Proving simultaneous positivity of linear forms
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Learning Decision Trees Using the Fourier Spectrum
• Decision trees
• Decision tree complexity and Betti numbers

This page was built for publication: Randomization and the computational power of analytic and algebraic decision trees