On the complexity of Diophantine geometry in low dimensions (extended abstract). (English) Zbl 1345.68181
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 527-536 (1999).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 11M26 | Nonreal zeros of \(\zeta (s)\) and \(L(s, \chi)\); Riemann and other hypotheses |
| 11U05 | Decidability (number-theoretic aspects) |
| 14G10 | Zeta functions and related questions in algebraic geometry (e.g., Birch-Swinnerton-Dyer conjecture) |
| 14G40 | Arithmetic varieties and schemes; Arakelov theory; heights |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
References:
| [1] | 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. |
| [2] | Apostol, Tom M., “Introduction to Analytic Number Theory,” Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. · Zbl 0335.10001 |
| [3] | Babai, L. and Moran, S., “Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes,” Journal of Computer and System Sciences, 36:254-276, 1988. 10.1016/0022-0000(88)90028-1 · Zbl 0652.03029 |
| [4] | Basu, S., Pollack, R., Roy, M.-F., “On the Combinatorial and Algebraic Complexity of Quantifier Elimination,” Journal of the ACM, Vol. 43, No. 6, November 1996, pp. 1002-1045. 10.1145/235809.235813 · Zbl 0885.68070 |
| [5] | Beauville, Arnaud, Complex Algebraic Surfaces, second edition, London Mathematical Society Student Texts, 34, Cambridge University Press, 1996. · Zbl 0849.14014 |
| [6] | Bini, Dario and Pan, Victor Y., Polynomial andMatrix Computations, Volume 1: Fundamental Algorithms, Progress in Theoretical Computer Science, Birkh iuser, 1994. · Zbl 0809.65012 |
| [7] | Blum, L., Cucker, F., Shub, M., Smale, S., Complexity and Real Computation, Springer-Verlag, 1998. · Zbl 0872.68036 |
| [8] | Brent, Richard P., “Fast Multiple-Precision Evaluation of Elementary Functions,” J. Assoc. Comput. Mach. 23 (1976), no. 2, pp. 242-251. 10.1145/321941.321944 · Zbl 0324.65018 |
| [9] | Burago, Yu. D. and Zalgaller, V. A., Geometric Inequalities, Grundlehren der mathematischen Wis senschaften 285, Springer-Verlag (1988). · Zbl 0633.53002 |
| [10] | Biirgisser, Peter, “Cook”s Versus Valiant’s Hypothesis,” Theoretical Computer Science, special issue in honor of Manuel Blum’s 60th birthday to appear. 10.1016/S0304-3975(99)00183-8 |
| [11] | Canny, John F., “The Complexity of Robot Motion Planning Problems,” ACM Doctoral Dissertation Award Series, ACM Press (1987). |
| [12] | , “Some Algebraic and Geometric Computations in PSPACE,” Proc. 20tn ACM Symp. Theory of Computing, Chicago (1988). 10.1145/62212.62257 |
| [13] | Canny, J. F., Kaltofen, E., and Lakshman, Y., “Solving Systems of Non-Linear Polynomial Equations Faster,” Proc. ACM Intern. Syrup. on Symbolic and Algebraic Computation, pp. 121-128, 1989. 10.1145/74540.74556 |
| [14] | Chan, T. M., “Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems,” Discrete Comput. Geom. 16 (1996), no. 4, pp. 369-387. · Zbl 0857.68112 |
| [15] | Cohen, Henri, A Course in Computational Number Theory, Graduate Texts in Mathematics, 138, Springer- Verlag, Berlin, 1993. · Zbl 0786.11071 |
| [16] | Dyer, M., Frieze, A., and Kannan, R., “A Random Polynomial-Time Algorithm for Approximating the Volume of Convex Bodies,” J. Assoc. Comput. Mach. 38 (1991), no. 1, pp. 1-17. 10.1145/102782.102783 · Zbl 0799.68107 |
| [17] | Dyer, M., Gritzmann, P., and Hufnagel, A., “On the Complexity o · Zbl 0909.68193 |
| [18] | Emiris, Ioannis Z. and Canny, John F., “Elficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume,” Journal of Symbolic Computation, vol. 20 (1995), pp. 117-149. 10.1006/jsco.1995.1041 · Zbl 0843.68036 |
| [19] | Ewald, Giinter, Combinatorial Convexity and Algebraic Geometry, Graduate Texts in Mathematics I68, Springer-Verlag, New York, 1996. · Zbl 0869.52001 |
| [20] | 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. · Zbl 0716.03023 |
| [21] | Gel’fand, I. M., Kapranov, M. M., a d Zelevinsky, A. V., Discriminants, Resultants and Multidimensional Determinants, Birkh user, Boston, I994. · Zbl 0827.14036 |
| [22] | 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. · Zbl 0819.52008 |
| [23] | Hartshorne, Robin, Algebraic Geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag. · Zbl 0531.14001 |
| [24] | Ierardi, Doug, “Quantifier Elimination in the Theory of an Algebraically-closed Field,” Proc. 21 ACM Syrup. Theory of Computing, Seattle (1989), pp. 138-147. 10.1145/73007.73020 |
| [25] | JS. JgL, Joseph, An Introduction to Parallel Algorithms, Addison-Wesley, 1992. · Zbl 0781.68009 |
| [26] | Jones, James P., “Classification of Quantifier Prefixes Over Diophantine Equations,” Zeitschr. f. math. Logik und Grundlagen d. Math., Bd. 27, pp. 403-410 (1981). · Zbl 0472.03034 |
| [27] | , “Universal Diophantine Equation,” Journal of Symbolic Logic, 47 (3), pp. 403-410 (1982). |
| [28] | 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. |
| [29] | Koiran, Pascal, “Hilbert”s NulIstellensatz is in the Polynomial Hierarchy,” DIMACS Technical Report 96- 27, July 1996. (Note: This preprint considerably improves the published version which appeared in Journal of Complexity in 1996.) 10.1006/jcom.1996.0019 · Zbl 0862.68053 |
| [30] | , “Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties,” Proceedings of the 38th Annual IEEE Computer Society Conference on Foundations of Computer Science (FOCS), Oct. 20-22, 1997, ACM Press. |
| [31] | 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. · Zbl 0362.12011 |
| [32] | Lenstra, A. K., Lenstra, H. W., Lov z, L., “Factoring Polynomials with Rational Coe icients,” Math. Ann. 261 (1982), pp. 515-534. · Zbl 0488.12001 |
| [33] | 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. |
| [34] | Malajovich-Mufioz, Gregorio, “On the Complexity of Path-Following Newton Algorithms for Solving Systems of Polynomial Equations with Integer Coefficients,” Ph.D. Thesis, U C Berkeley, 1994, University Microfilms International, Michigan. |
| [35] | Matiyasevich, Yuri V., “The Diophantineness of Enumerable Sets,” Soviet Math. Dokl. 11 (1970), pp. 354-358. · Zbl 0212.33401 |
| [36] | .... , Hilbert ’s Tenth Problem, MIT Press (1993). · Zbl 0790.03008 |
| [37] | 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). |
| [38] | Mignotte, Maurice, Mathematics for Computer Algebra, translated from the French by Catherine Mignotte, Springer-Verlag, New York, 1992. · Zbl 0741.11002 |
| [39] | Mumford, David, Algebraic Geometry {: Complex Projective Varieties, Reprint of the I976 edition, Classics in Mathematics, Springer-Verlag, Berlin, 1995.} · Zbl 0821.14001 |
| [40] | Neff, C. Andrew, “Specified Precision Root Isolation is in NC,” J. of Computer and System Sci. 48, pp. 429- 463, 1994. 10.1016/S0022-0000(05)80061-3 · Zbl 0806.68054 |
| [41] | Neff, C. Andrew and Reif, John, “An Efficient Algorithm for the Complex Roots Problem,” Journal of Complexity 12 (1996), no. 2, pp. 81-115. 10.1006/jcom.1996.0008 · Zbl 0888.12005 |
| [42] | Papadimitriou, Christos H., Computational Complexity, Addison-Wesley, 1995. · Zbl 0833.68049 |
| [43] | Pratt, Vaughan 1 ., “Every Prime has a Succinct Certificate,” SIAM J. Comput. 4 (1975), pp. 327-340. · Zbl 0316.68031 |
| [44] | Renegar, James, “On the Computational Complexity and Geometry of the First-Order Theory of the Reals: I-III,” J. Symbolic Comput. 13 (1992), no. 3, pp. 255-352. 10.1016/S0747-7171(10)80003-3 |
| [45] | Rojas, J. Maurice, “Uncomputably Large Integral Points on Algebraic Plane Curves?,” Theoretical Computer Science, special issue in honor of Manuel Blum’s 60th birthday, to appear. Also available from http://xxx, lanl. gov/math. AG/9809009. 10.1016/S0304-3975(99)00188-7 |
| [46] | , “Solving Degenerate Sparse Polynomial Systems Faster,” Journal of Symbolic Computation, special issue on elimination theory, to appear. Also available from http://xxx, lanl. gov/math. AG/9809071. 10.1006/jsco.1998.0271 |
| [47] | Rudin, Walter, Principles of Mathematical Analysis, 3rd edition, McGraw-Hili, 1976. · Zbl 0346.26002 |
| [48] | Schicho, Josef, “Rational Parametrization of Surfaces,” Journal of Symbolic Computation 26 (I998), no. 1, pp. 1-29. 10.1006/jsco.1997.0199 · Zbl 0924.14027 |
| [49] | Schinzel, Andrzej, Selected Topics on Polynomials, Univ. of Michigan Press, Ann Arbor, 1982. · Zbl 0487.12002 |
| [50] | Schwartz, J., “Fast Probabilistic Algorithms for Verification of Polynomial Identities,” J. of the ACM 27, pp. 701-717, 1980. 10.1145/322217.322225 · Zbl 0452.68050 |
| [51] | Silverman, Joseph H., The Arithmetic of Elliptic Curves, corrected reprint of the 1986 original, Graduate Texts in Mathematics 106, Springer-Verlag (1995). |
| [52] | ...... , “On the Distribution of Integer Pointson Curves of Genus Zero,” Theoretical Computer Science, special issue in honor of Manuel Blum’s 60th birthday, to appear. 10.1016/S0304-3975(99)00189-9 |
| [53] | 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. · Zbl 0916.13008 |
| [54] | Tung, Shih-Ping, “Computational Complexities of Diophantine Equations with Parameters,” Journal of Algorithms 8, pp. 324-336 (1987). 10.1016/0196-6774(87)90013-7 · Zbl 0641.03009 |
| [55] | Weinberger, Peter, “Finding the Number of Factors of a Polynomial,” Journal of Algorithms, 5:180- 186, 1984. · Zbl 0542.12001 |
| [56] | Zachos, S., “ProbabiIistic Quantifers, Adversaries, and Complexity Classes: An Overview,” Proc. 1st Structure in Complexity Theory Conference, voI. 223, Lecture Notes in Computer Science, Springer-Verlag, 1986. · Zbl 0632.03035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
