On the complexity of diophantine geometry in low dimensions (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

On the complexity of diophantine geometry in low dimensions (extended abstract)

Full text

Pdf (881 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 527 - 536

Year of Publication: 1999

ISBN:1-58113-067-8

Author

J. Maurice Rojas

Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Citation Count: 0

Additional Information:

references 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/301250.301395 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.

	AGR94	Amato, N. M., Goodrich, M. T., and Ramos, E. A., "Parallel Algorithms for Higher-Dimensional Convex Hulls," Proceedings of the 35th Annual Symposium on Foundations of Computer Science (Nov. 20-22, 1994, Santa Fe, New Mexico), pp. 683-694, IEEE Computer Society Press.
	Apo90	Apostol, Tom M., "Introduction to Analytic Number Theory," Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976.
	BM88	László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
	BPR96	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	Bea96	Beauville, Arnaud, Complex Algebraic Surfaces, second edition, London Mathematical Society Student Texts, 34, Cambridge University Press, 1996.
	BP94	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	BSS98	Lenore Blum , Felipe Cucker , Michael Shub , Steve Smale, Complexity and real computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	Bre76	Richard P. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, Journal of the ACM (JACM), v.23 n.2, p.242-251, April 1976 [doi>10.1145/321941.321944]
	BZ88	Burago, Yu. D. and Zalgaller, V. A., Geometric Inequalities, Grundlehren der mathematischen Wis~ senschaften 285, Springer-Verlag (1988).
	Bür99	Peter Bürgisser, Cook's versus Valiant's hypothesis, Theoretical Computer Science, v.235 n.1, p.71-88, March 17, 2000 [doi>10.1016/S0304-3975(99)00183-8]
	Can87	Canny, John F., "The Complexity of Robot Motion Planning Problems," ACM Doctoral Dissertation Award Series, ACM Press (1987).
	Can88	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
	CKL89	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74556]
	Cha96	Chan, T. M., "Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems," Discrete Comput. Geom. 16 (1996), no. 4, pp. 369-387.
	Coh93	Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
	DFK91	Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
	DGH98	Martin Dyer , Peter Gritzmann , Alexander Hufnagel, On The Complexity of Computing Mixed Volumes, SIAM Journal on Computing, v.27 n.2, p.356-400, April 1998 [doi>10.1137/S0097539794278384]
	EC95	Ioannis Z. Emiris , John F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, Journal of Symbolic Computation, v.20 n.2, p.117-149, Aug. 1995 [doi>10.1006/jsco.1995.1041]
	Ewa96	Ewald, Giinter, Combinatorial Convexity and Algebraic Geometry, Graduate Texts in Mathematics I68, Springer-Verlag, New York, 1996.
	FGM90	Fichtas, N., Galligo, A., and Morgenstern, J., "Precise Sequential and Parallel Complexity Bounds for Quantifier Elimination Over Algebraically Closed Fields," Journal of Pure and Applied Algebra, 67:1-14, 1990.
	GKZ94	Gel'fand, I. M., Kapranov, M. M., a~d Zelevinsky, A. V., Discriminants, Resultants and Multidimensional Determinants, Birkh~user, Boston, I994.
	GK94	Gritzmann: Peter and Klee, Victor, "On the Complexity of Some Basic Problems in Computational Convexity II: Volume and Mixed Volumes," Polytopes: Abstract, Convex, and Computational (Scaxborough, ON, 1993), pp. 373-466, NATO Adv. Sci. Inst. Set. C Math. Phys. Sci., 440, Kluwer Acad. Publ., Dordrecht, 1994.
	Har77	Hartshorne, Robin, Algebraic Geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag.
	Ier89	D. Ierardi, Quantifier elimination in the theory of an algebraically-closed field, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.138-147, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73020]
	JáJá92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	Jon81	Jones, James P., "Classification of Quantifier Prefixes Over Diophantine Equations," Zeitschr. f. math. Logik und Grundlagen d. Math., Bd. 27, pp. 403-410 (1981).
	Jon82	, "Universal Diophantine Equation,'' Journal of Symbolic Logic, 47 (3), pp. 403-410 (1982).
	Kho78	Khovanskii, A. G., "Newton Polyhedra and the Genus of Complete Intersections," Functional Analysis (translated from Russian), Vol. 12, No. 1, January- March (1978), pp. 51-61.
	Koi96	Pascal Koiran, Hilbert's Nullstellensatz is in the polynomial hierarchy, Journal of Complexity, v.12 n.4, p.273-286, Dec. 1996 [doi>10.1006/jcom.1996.0019]
	Koi97	P. Koiran, Randomized and deterministic algorithms for the dimension of algebraic varieties, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.36, October 19-22, 1997
	LO77	Lagarias, Jeff and Odlyzko, Andrew, "Effective Versions of the Chebotarev Density Theorem," Algebraic Number Fields: L-functions and Galois Properties (Proc. Sympos. Univ. Durham, Durham, 1975), pp. 409-464, Academic Press, London, 1977.
	LLL82	Lenstra, A. K., Lenstra, H. W., Lov~z, L., "Factoring Polynomials with Rational Coe~icients," Math. Ann. 261 (1982), pp. 515-534.
	Len98	Lenstra, Hendrik W., "Finding Small Degree Factors of Lacunary Polynomials," Number Theory in Progress, proceedings of a meeting in honor of the 70th birthday of Andrej Schnizel, W. de Gruyter, to appear.
	Mal94	Gregorio Malajovich-Munoz , Steve Smale, On the complexity of path-following newton algorithms for solving systems of polynomial equations with integer coefficients, 1993
	Mat70	Matiyasevich, Yuri V., "The Diophantineness of Enumerable Sets," Soviet Math. Dokl. 11 (1970), pp. 354-358.
	Mat93	Yuri V. Matiyasevich, Hilbert's tenth problem, MIT Press, Cambridge, MA, 1993
	MR74	Matiyasevich, Yuri V. and Robinson, Julia "Two Universal 3-Quantifier Representations of Recursively Enumerable Sets," Teoriya Algorifmov i Matematicheskaya Logika (Volume dedicated to A. A. Markov), pp. 112-123, Vychislitel'ny~ Tsentr, Akademiya Nauk SSSR, Moscow (Russian).
	Mig92	Maurice Mignotte, Mathematics for computer algebra, Springer-Verlag New York, Inc., New York, NY, 1992
	Mum95	Mumford, David, Algebraic Geometry {: Complex Projective Varieties, Reprint of the I976 edition, Classics in Mathematics, Springer-Verlag, Berlin, 1995.
	Nef94	C. Andrew Neff, Specified precision polynomial root isolation is in NC, Journal of Computer and System Sciences, v.48 n.3, p.429-463, June 1994 [doi>10.1016/S0022-0000(05)80061-3]
	NR96	C. Andrew Neff , John H. Reif, An efficient algorithm for the complex roots problem, Journal of Complexity, v.12 n.2, p.81-115, June 1996 [doi>10.1006/jcom.1996.0008]
	Pap95	Papadimitriou, Christos H., Computational Complexity, Addison-Wesley, 1995.
	Pra75	Pratt, Vaughan 1~., "Every Prime has a Succinct Certificate,' SIAM J. Comput. 4 (1975), pp. 327-340.
	Ren92	James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
	Roj99a	J. Maurice Rojas, Uncomputably large integral points on algebraic plane curves?, Theoretical Computer Science, v.235 n.1, p.145-162, March 17, 2000 [doi>10.1016/S0304-3975(99)00188-7]
	Roj99b	J. Maurice Rojas, Solving degenerate sparse polynomial systems faster, Journal of Symbolic Computation, v.28 n.1-2, p.155-186, July/Aug. 1999 [doi>10.1006/jsco.1998.0271]
	Rud76	Rudin, Walter, Principles of Mathematical Analysis, 3rd edition, McGraw-Hili, 1976.
	Sch98	Josef Schicho, Rational parametrization of surfaces, Journal of Symbolic Computation, v.26 n.1, p.1-29, July 1998 [doi>10.1006/jsco.1997.0199]
	Sch82	Schinzel, Andrzej, Selected Topics on Polynomials, Univ. of Michigan Press, Ann Arbor, 1982.
	Sch80	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]
	Sil95	Silverman, Joseph H., The Arithmetic of Elliptic Curves, corrected reprint of the 1986 original, Graduate Texts in Mathematics 106, Springer-Verlag (1995).
	Sil99	Joseph H. Silverman, On the distribution of integer points on curves of genus zero, Theoretical Computer Science, v.235 n.1, p.163-170, March 17, 2000 [doi>10.1016/S0304-3975(99)00189-9]
	Stu98	Sturmfels, Bernd, "Introduction to Resultants," Applications of Computational Algebraic Geometry (San Diego, CA, 1997), pp. 25-39, Proc. Sympos. Appl. Math., 53, Amer. Math. Soc., Providence, ILl, 1998.
	Tun87	S. P. Tung, Computational complexities of diophantine equations with parameters, Journal of Algorithms, v.8 n.5, p.324-336, Sept. 1987 [doi>10.1016/0196-6774(87)90013-7]
	Wei84	Weinberger, Peter, "Finding the Number of Factors of a Polynomial," Journal of Algorithms, 5:180- 186, 1984.
	Zac86	S Zachos, Probabilistic quantifiers, adversaries, and complexity classes: an overview, Proc. of the conference on Structure in complexity theory, p.383-400, June 1986, Berkeley, California, United States