Name
Abstract | ||
|---|---|---|
We show lower bounds for the parallel complexity of membership problems in semialgebraic sets. Our lower bounds are obtained from the Euler characteristic and the sum of Betti numbers. We remark that these lower bounds are polynomial (an square root) in the sequential lower bounds obtained by Andrew C.C. Yao. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/s002000050018 | Appl. Algebra Eng. Commun. Comput. |
Keywords | Field | DocType |
Parallel complexity,Algebraic complexity theory,Arithmetic networks,Semi-algebraic sets,Borel-Moore homology | Discrete mathematics,Combinatorics,Betti number,Polynomial,Euler characteristic,Borel–Moore homology,Square root,Real algebraic geometry,Mathematics,Parallel complexity | Journal |
Volume | Issue | Citations |
7 | 1 | 13 |
PageRank | References | Authors |
1.38 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josè L. Montaña | 1 | 82 | 15.50 |
| Jose Enrique Morais | 2 | 26 | 2.44 |
| Luis Miguel Pardo | 3 | 141 | 15.63 |