Complexity lower bounds for computation trees with elementary transcendental function gates
From MaRDI portal
Publication:1365876
DOI10.1016/0304-3975(95)00159-XzbMATH Open0877.68086DBLPjournals/tcs/GrigorievV96WikidataQ30048515 ScholiaQ30048515MaRDI QIDQ1365876FDOQ1365876
Authors: Dima Grigoriev, Nicolai Vorobjov 
Publication date: 9 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
- Lower bounds on testing membership to a polyhedron by algebraic decision trees
- On topological lower bounds for algebraic computation trees
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
Cites Work
- Semianalytic and subanalytic sets
- On the Betti Numbers of Real Varieties
- Decision tree complexity and Betti numbers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sur la complexité du principe de Tarski-Seidenberg
- Topological Properties of Subanalytic Sets
- Solving systems of polynomial inequalities in subexponential time
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Complexity of deciding Tarski algebra
- Complements of subanalytic sets and existential formulas for analytic functions
- Title not available (Why is that?)
- Real-Analytic Desingularization and Subanalytic Sets: An Elementary Approach
- Finding irreducible components of some real transcendental varieties
- Complexity lower bounds for computation trees with elementary transcendental function gates
- Lower bounds on testing membership to a polyhedron by algebraic decision trees
- On the Polyhedral Decision Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of stratifications of semi-Pfaffian sets
- Title not available (Why is that?)
- The complexity of deciding consistency of systems of polynomials in exponent inequalities
- On Computing Algebraic Functions Using Logarithms and Exponentials
Cited In (8)
- Randomization and the computational power of analytic and algebraic decision trees
- Instability, complexity, and evolution
- Complexity lower bounds for computation trees with elementary transcendental function gates
- On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations
- Rough analysis of computation trees
- Complexity of gene circuits, Pfaffian functions and the morphogenesis problem.
- Algorithms and complexity in biological pattern formation problems
- Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
This page was built for publication: Complexity lower bounds for computation trees with elementary transcendental function gates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1365876)
