Test complexity of generic polynomials. Bürgisser, P., Lickteig, T., & Shub, M. J. Compl., 8(3):203-215, 1992. ![Test complexity of generic polynomials [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex We investigate the complexity of algebraic decision trees deciding membership in a hypersurface $X$ in $\mathbb C^m$. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurface $X$ in $\mathbb C^m$. Over the reals, where in addition to equality branching also $<$-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces $X$ in $\mathbb R^m$. In the case $m=1$ we give also a lower bound for finite subsets $X$ in $\mathbb R$.
@ARTICLE{BLS-Test-Complexity-Of-Generic-Polynomials,
URL={http://www.sciencedirect.com/science/article/pii/0885064X92900224},
JOURNAL={J. Compl.},
TITLE={Test complexity of generic polynomials},
DOI={10.1016/0885-064X(92)90022-4},
VOLUME={8},
ABSTRACT={We investigate the complexity of algebraic decision trees deciding membership in a hypersurface $X$ in $\mathbb C^m$. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurface $X$ in $\mathbb C^m$. Over the reals, where in addition to equality branching also $<$-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces $X$ in $\mathbb R^m$. In the case $m=1$ we give also a lower bound for finite subsets $X$ in $\mathbb R$.},
AUTHOR={Peter Bürgisser and Thomas Lickteig and Michael Shub},
YEAR={1992},
PAGES={203-215},
NUMBER={3}
}
Downloads: 0
{"_id":"3wh2vhDeBCXGD255q","bibbaseid":"brgisser-lickteig-shub-testcomplexityofgenericpolynomials-1992","downloads":0,"creationDate":"2017-01-04T12:11:10.529Z","title":"Test complexity of generic polynomials","author_short":["Bürgisser, P.","Lickteig, T.","Shub, M."],"year":1992,"bibtype":"article","biburl":"http://www3.math.tu-berlin.de/algebra/static/papers.parsed.bib","bibdata":{"bibtype":"article","type":"article","url":"http://www.sciencedirect.com/science/article/pii/0885064X92900224","journal":"J. Compl.","title":"Test complexity of generic polynomials","doi":"10.1016/0885-064X(92)90022-4","volume":"8","abstract":"We investigate the complexity of algebraic decision trees deciding membership in a hypersurface $X$ in $\\mathbb C^m$. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurface $X$ in $\\mathbb C^m$. Over the reals, where in addition to equality branching also $<$-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces $X$ in $\\mathbb R^m$. In the case $m=1$ we give also a lower bound for finite subsets $X$ in $\\mathbb R$.","author":[{"firstnames":["Peter"],"propositions":[],"lastnames":["Bürgisser"],"suffixes":[]},{"firstnames":["Thomas"],"propositions":[],"lastnames":["Lickteig"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Shub"],"suffixes":[]}],"year":"1992","pages":"203-215","number":"3","bibtex":"@ARTICLE{BLS-Test-Complexity-Of-Generic-Polynomials,\r\n URL={http://www.sciencedirect.com/science/article/pii/0885064X92900224},\r\n JOURNAL={J. Compl.},\r\n TITLE={Test complexity of generic polynomials},\r\n DOI={10.1016/0885-064X(92)90022-4},\r\n VOLUME={8},\r\n ABSTRACT={We investigate the complexity of algebraic decision trees deciding membership in a hypersurface $X$ in $\\mathbb C^m$. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurface $X$ in $\\mathbb C^m$. Over the reals, where in addition to equality branching also $<$-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces $X$ in $\\mathbb R^m$. In the case $m=1$ we give also a lower bound for finite subsets $X$ in $\\mathbb R$.},\r\n AUTHOR={Peter Bürgisser and Thomas Lickteig and Michael Shub},\r\n YEAR={1992},\r\n PAGES={203-215},\r\n NUMBER={3}\r\n}\r\n\r\n","author_short":["Bürgisser, P.","Lickteig, T.","Shub, M."],"key":"BLS-Test-Complexity-Of-Generic-Polynomials","id":"BLS-Test-Complexity-Of-Generic-Polynomials","bibbaseid":"brgisser-lickteig-shub-testcomplexityofgenericpolynomials-1992","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/0885064X92900224"},"downloads":0,"html":""},"search_terms":["test","complexity","generic","polynomials","bürgisser","lickteig","shub"],"keywords":[],"authorIDs":[],"dataSources":["mFLw2PzriqAWWFuqX"]}