@ARTICLE{BL-Verification-Complexity-Of-Linear-Prime-Ideals,
 JOURNAL={J. Pure Appl. Alg.},
 TITLE={Verification complexity of linear prime ideals},
 URL={http://www.sciencedirect.com/science/article/pii/002240499290059O},
 VOLUME={81},
 AUTHOR={Peter Bürgisser and Thomas Lickteig},
 YEAR={1992},
 ABSTRACT={The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset $X$ in $R^m$ where $R$ is a real or algebraically closed field. We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of linear type generalizing a result by Winograd (1970). As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms: 

For deciding whether a number is a zero of several polynomials - if this number and the coefficients of these polynomials are given as input data - evaluation of each polynomial with Horner's rule and then testing the values for zero is optimal. 
 
For verifying that a vector satisfies a system of linear equations - given the vector and the coefficients of the system as input data - the natural algorithm is optimal.},
 PAGES={247-267}
}

{"_id":"GMpttA6osNSNGQsdk","bibbaseid":"brgisser-lickteig-verificationcomplexityoflinearprimeideals-1992","downloads":0,"creationDate":"2017-01-04T12:11:10.528Z","title":"Verification complexity of linear prime ideals","author_short":["Bürgisser, P.","Lickteig, T."],"year":1992,"bibtype":"article","biburl":"http://www3.math.tu-berlin.de/algebra/static/papers.parsed.bib","bibdata":{"bibtype":"article","type":"article","journal":"J. Pure Appl. Alg.","title":"Verification complexity of linear prime ideals","url":"http://www.sciencedirect.com/science/article/pii/002240499290059O","volume":"81","author":[{"firstnames":["Peter"],"propositions":[],"lastnames":["Bürgisser"],"suffixes":[]},{"firstnames":["Thomas"],"propositions":[],"lastnames":["Lickteig"],"suffixes":[]}],"year":"1992","abstract":"The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset $X$ in $R^m$ where $R$ is a real or algebraically closed field. We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of linear type generalizing a result by Winograd (1970). As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms: For deciding whether a number is a zero of several polynomials - if this number and the coefficients of these polynomials are given as input data - evaluation of each polynomial with Horner's rule and then testing the values for zero is optimal. For verifying that a vector satisfies a system of linear equations - given the vector and the coefficients of the system as input data - the natural algorithm is optimal.","pages":"247-267","bibtex":"@ARTICLE{BL-Verification-Complexity-Of-Linear-Prime-Ideals,\r\n JOURNAL={J. Pure Appl. Alg.},\r\n TITLE={Verification complexity of linear prime ideals},\r\n URL={http://www.sciencedirect.com/science/article/pii/002240499290059O},\r\n VOLUME={81},\r\n AUTHOR={Peter Bürgisser and Thomas Lickteig},\r\n YEAR={1992},\r\n ABSTRACT={The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset $X$ in $R^m$ where $R$ is a real or algebraically closed field. We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of linear type generalizing a result by Winograd (1970). As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms: \r\n\r\nFor deciding whether a number is a zero of several polynomials - if this number and the coefficients of these polynomials are given as input data - evaluation of each polynomial with Horner's rule and then testing the values for zero is optimal. \r\n \r\nFor verifying that a vector satisfies a system of linear equations - given the vector and the coefficients of the system as input data - the natural algorithm is optimal.},\r\n PAGES={247-267}\r\n}\r\n\r\n","author_short":["Bürgisser, P.","Lickteig, T."],"key":"BL-Verification-Complexity-Of-Linear-Prime-Ideals","id":"BL-Verification-Complexity-Of-Linear-Prime-Ideals","bibbaseid":"brgisser-lickteig-verificationcomplexityoflinearprimeideals-1992","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/002240499290059O"},"downloads":0,"html":""},"search_terms":["verification","complexity","linear","prime","ideals","bürgisser","lickteig"],"keywords":[],"authorIDs":[],"dataSources":["mFLw2PzriqAWWFuqX"]}