Uniform closure properties of P-computable functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Uniform closure properties of P-computable functions

Full text

Pdf (662 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 330 - 337

Year of Publication: 1986

ISBN:0-89791-193-8

Author

E Kaltofen

Rensselaer Polytechnic Institute, Dept. of Computer Science, Troy, New York and Mathematical Sciences Research Institute, Berkeley, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 16, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/12130.12163 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. Valiant, "Reducibility by algebraic projections," L'Enseignemsnt math6matique, vol. 28, pp. 253-268, 1982.
	2	E Kaltofen, Computing with polynomials given by straight-line programs I: greatest common divisors, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.131-142, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22160]
	3	E. Kaltofen, "Computing with polynomials given by straight-line programs lI; Sparse factorization," Proc. 26th IEEE Syrup. Foundation.s Comp. Sci., pp. 451-458, 1985.
	4	Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
	5	A. K. Lenstra, H. W. Lenstra Jr., and L. Lov~sz, "Factoring polynomials with rational coefficients," Math. Ann., vol. 261, pp. 515-534, 1982.
	6	E. Kaltofen, "Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization," SIAM J. Comp., vol. 14, pp. 469-489, 1985.
	7	Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]
	8	E. Kaltofen, "Effective Hilbert irreducibility," Information and Control, vol. 65, p. in press, 1985.
	9	V. Strassen, "Vermeidung yon Divisionen," J. reins u. angew. Math., vol. 264, pp. 182-202, 1973.
	10	L. Hyafil, "On the parallel evaluation of multivariate polynomials," SIAM J. Comp., vol. 8, pp. 120-123, 1979.
	11	L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, "Fast parallel computation of polynomials using few processors," SIAM J. Comp., vo}. 12, pp. 641-644, 1983.
	12	A. SchSnhage, "Schnelle Multiplikation von Polynomen liber KSrpern der Charakteristik 2," Acta Inf., vol. 7, pp. 395-398, 1977.
	13	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	14	A. FrShlich and J. C. Shepherdson, "Effective procedures in field theory," Phil. Trans. Roy. Sot., Ser. A, vol. 248, pp. 407-432, 1955/56.
	15	Richard J. Lipton , Larry J. Stockmeyer, Evaluation of polynomials with super-preconditioning, Proceedings of the eighth annual ACM symposium on Theory of computing, p.174-180, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803645]
	16	C. P. Schnorr, "Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials," Theoretical Cutup. Sei., vol. 7, pp. 251-261, 1978.
	17	R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun, "Fast solution of Toeplit~ systems of equations and computation of Pad~ approximants," J. AIgorithnu, vol. 1, pp. 259-295, 1980.
	18	D. E. Knuth, "The analysis of algorithms," Acres du eongr~6 international de6 Math}maticiene, vol. 3, pp. 269-274, Nice, France, 1970.
	19	A. SchSnhage, "Schnelle Kettenbruchentwicklungen," Aeta Inf., vol. 1, pp. 139-144, 1971.
	20	R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
	21	Stephen R. Czapor , Keith O. Geddes, A Comparison of Algorithms for the Symbolic Computation of Padé Approximants, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.248-259, July 09-11, 1984
	22	Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
	23	Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806338]
	24	S. Landau, "Factoring polynomials over algebraic number fields," SIAM J. Comp., vol. 14, pp. 184-195, 1985.
	25	Joachim von zur Gathen, Parallel algorithms for algebraic problems, SIAM Journal on Computing, v.13 n.4, p.802-824, Nov. 1984 [doi>10.1137/0213050]
	26	P. J. Weinberger, "Finding the number of factors of a polynomial," J. Algorithmz, vol. 5, pp. 180-186, 1984.

CITED BY 5

	T. Freeman , G. Imirzian , E. Kaltofen, A system for manipulating polynomials given by straight-line programs, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.169-175, July 21-23, 1986, Waterloo, Ontario, Canada
	E. Kaltofen, Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.443-452, January 1987, New York, New York, United States
	Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988
	Timothy S. Freeman , Gregory M. Imirzian , Erich Kaltofen , Lakshman Yagati, Dagwood: a system for manipulating polynomials given by straight-line programs, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.218-240, Sept. 1988
	Guillaume Malod , Natacha Portier, Characterizing Valiant's algebraic complexity classes, Journal of Complexity, v.24 n.1, p.16-38, February, 2008