ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Lower bounds for arithmetic networks II: Sum of Betti numbers (1996)

Montaña, J. L. ; Morais, J. E. ; Pardo, Luis M.

Springer

Applicable algebra in engineering, communication and computing 7 (1996), S. 41-51

add to mindlist on the mindlist

Details

ISSN: 1432-0622

Keywords: Parallel complexity ; Algebraic complexity theory ; Arithmetic networks ; Semi-algebraic sets ; Borel-Moore homology

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics , Technology

Notes: 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.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01613615

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit