Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14867

Title: Software Engineering and complexity in effective Algebraic Geometry
Authors: Heintz, Joos
Kuijpers, Bart
Paredes, Andres Rojas
Issue Date: 2013
Citation: JOURNAL OF COMPLEXITY, 29 (1), p. 92-138
Abstract: One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective Algebraic Geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal.
URI: http://hdl.handle.net/1942/14867
DOI: 10.1016/j.jco.2012.04.005
ISI #: 000313312400006
ISSN: 0885-064X
Category: A1
Type: Journal Contribution
Validation: ecoom, 2014
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
journal version466.31 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.