On a problem posed by Steve Smale

Abstract

The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of $n$ complex polynomials in $n$ unknowns in time polynomial, on the average, in the size $N$ of the input system. A partial solution to this problem was given by Carlos Beltrán and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that efficiently implements a nonconstructive idea of Mike Shub. This algorithm is then used in a randomized algorithm, call it LV, à la Beltrán-Pardo. Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and $\sigma^{-1}$, where $\sigma$ controls the size of of the random perturbation of the input systems. Thirdly, we perform a condition-based analysis of LV. That is, we give a bound, for each system $f$, of the expected running time of LV with input $f$. In addition to its dependence on $N$ this bound also depends on the condition of $f$. Fourthly, and to conclude, we return to Smale’s 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is $N^{\mathcal{O}(\log\log N)}$. This is nearly a solution to Smale’s 17th problem.

  • [AKS:04] Go to document M. Agrawal, N. Kayal, and N. Saxena, "PRIMES is in P," Ann. of Math., vol. 160, iss. 2, pp. 781-793, 2004.
    @article {AKS:04, MRKEY = {2123939},
      AUTHOR = {Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin},
      TITLE = {P{RIMES} is in {P}},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {160},
      YEAR = {2004},
      NUMBER = {2},
      PAGES = {781--793},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {11Y11 (11A51 68Q15 68Q25)},
      MRNUMBER = {2123939},
      MRREVIEWER = {Carl Pomerance},
      DOI = {10.4007/annals.2004.160.781},
      ZBLNUMBER = {1071.11070},
      }
  • [AmelunxenBuergisser:08] Go to document D. Amelunxen and P. Bürgisser, "Robust smoothed analysis of a condition number of linear programming," Math. Program., Ser. A.
    @article{AmelunxenBuergisser:08,
      author={Amelunxen, D and Bürgisser, P.},
      TITLE={Robust smoothed analysis of a condition number of linear programming},
      JOURNAL={Math. Program., Ser. A},
      DOI={10.1007/s10107-010-0346-x},
      }
  • [bast:83] Go to document W. Baur and V. Strassen, "The complexity of partial derivatives," Theoret. Comput. Sci., vol. 22, iss. 3, pp. 317-330, 1983.
    @article {bast:83, MRKEY = {0693063},
      AUTHOR = {Baur, Walter and Strassen, Volker},
      TITLE = {The complexity of partial derivatives},
      JOURNAL = {Theoret. Comput. Sci.},
      FJOURNAL = {Theoretical Computer Science},
      VOLUME = {22},
      YEAR = {1983},
      NUMBER = {3},
      PAGES = {317--330},
      ISSN = {0304-3975},
      CODEN = {TCSDI},
      MRCLASS = {68C25 (12-03 12F99)},
      MRNUMBER = {0693063},
      DOI = {10.1016/0304-3975(83)90110-X},
      ZBLNUMBER = {0498.68028},
      }
  • [BeltranPardo08] Go to document C. Beltrán and L. M. Pardo, "On Smale’s 17th problem: a probabilistic positive solution," Found. Comput. Math., vol. 8, iss. 1, pp. 1-43, 2008.
    @article {BeltranPardo08, MRKEY = {2403529},
      AUTHOR = {Beltr{á}n, Carlos and Pardo, Luis Miguel},
      TITLE = {On {S}male's 17th problem: a probabilistic positive solution},
      JOURNAL = {Found. Comput. Math.},
      FJOURNAL = {Foundations of Computational Mathematics. The Journal of the Society for the Foundations of Computational Mathematics},
      VOLUME = {8},
      YEAR = {2008},
      NUMBER = {1},
      PAGES = {1--43},
      ISSN = {1615-3375},
      MRCLASS = {65H10 (68W20)},
      MRNUMBER = {2403529},
      MRREVIEWER = {Jan M. Verschelde},
      DOI = {10.1007/s10208-005-0211-0},
      ZBLNUMBER = {1153.65048},
      }
  • [BePa08a] Go to document C. Beltrán and L. M. Pardo, "Smale’s 17th problem: average polynomial time to compute affine and projective solutions," J. Amer. Math. Soc., vol. 22, iss. 2, pp. 363-385, 2009.
    @article {BePa08a, MRKEY = {2476778},
      AUTHOR = {Beltr{á}n, Carlos and Pardo, Luis Miguel},
      TITLE = {Smale's 17th problem: average polynomial time to compute affine and projective solutions},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {22},
      YEAR = {2009},
      NUMBER = {2},
      PAGES = {363--385},
      ISSN = {0894-0347},
      MRCLASS = {90C30 (14Q20 65H20 68Q25)},
      MRNUMBER = {2476778},
      MRREVIEWER = {Jan M. Verschelde},
      DOI = {10.1090/S0894-0347-08-00630-9},
      ZBLNUMBER = {1206.90173},
      }
  • [BePa08b] Go to document C. Beltrán and L. M. Pardo, "Fast linear homotopy to find approximate zeros of polynomial ʊʊʊʊʊʊʳystems," Found. Comput. Math., vol. 11, iss. 1, pp. 95-129, 2011.
    @article {BePa08b,
      author = {Beltr{á}n, Carlos and Pardo, Luis Miguel},
      TITLE = {Fast linear homotopy to find approximate zeros of polynomial systems},
      JOURNAL = {Found. Comput. Math.},
      VOLUME = {11},
      YEAR = {2011},
      NUMBER = {1},
      PAGES = {95--129},
      ISSN = {1615-3375},
      MRCLASS = {65H20 (13P15 65H10 65Y20)},
      MRNUMBER = {2754191},
      MRREVIEWER = {Mihai Cipu},
      DOI = {10.1007/s10208-010-9078-9},
      }
  • [Bez7] Go to document C. Beltrán and M. Shub, "Complexity of Bezout’s theorem. VII. Distance estimates in the condition metric," Found. Comput. Math., vol. 9, iss. 2, pp. 179-195, 2009.
    @article {Bez7, MRKEY = {2496559},
      AUTHOR = {Beltr{á}n, Carlos and Shub, Michael},
      TITLE = {Complexity of {B}ezout's theorem. {VII}. {D}istance estimates in the condition metric},
      JOURNAL = {Found. Comput. Math.},
      FJOURNAL = {Foundations of Computational Mathematics. The Journal of the Society for the Foundations of Computational Mathematics},
      VOLUME = {9},
      YEAR = {2009},
      NUMBER = {2},
      PAGES = {179--195},
      ISSN = {1615-3375},
      MRCLASS = {65H10 (68Q25)},
      MRNUMBER = {2496559},
      MRREVIEWER = {Guillermo Matera},
      DOI = {10.1007/s10208-007-9018-5},
      }
  • [bcss:95] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, New York: Springer-Verlag, 1998.
    @book {bcss:95, MRKEY = {1479636},
      AUTHOR = {Blum, Lenore and Cucker, Felipe and Shub, Michael and Smale, Steve},
      TITLE = {Complexity and Real Computation},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1998},
      PAGES = {xvi+453},
      ISBN = {0-387-98281-7},
      MRCLASS = {68Q15 (03D15 13P99 14P99 65Y20 68-02)},
      MRNUMBER = {1479636},
      MRREVIEWER = {1479636r},
      ZBLNUMBER = {0872.68036},
      }
  • [bss:89] Go to document L. Blum, M. Shub, and S. Smale, "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines," Bull. Amer. Math. Soc., vol. 21, iss. 1, pp. 1-46, 1989.
    @article {bss:89, MRKEY = {0974426},
      AUTHOR = {Blum, Lenore and Shub, Mike and Smale, Steve},
      TITLE = {On a theory of computation and complexity over the real numbers: {NP}-completeness, recursive functions and universal machines},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {21},
      YEAR = {1989},
      NUMBER = {1},
      PAGES = {1--46},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {68Q10 (03D15 03D75 03D80 03F60 68Q15 68Q25)},
      MRNUMBER = {0974426},
      MRREVIEWER = {John Michael Robson},
      DOI = {10.1090/S0273-0979-1989-15750-9},
      ZBLNUMBER = {0681.03020},
      }
  • [BC:10] Go to document P. Bürgisser and F. Cucker, "Smoothed analysis of Moore-Penrose inversion," SIAM J. Matrix Anal. Appl., vol. 31, iss. 5, pp. 2769-2783, 2010.
    @article {BC:10, MRKEY = {2740632},
      AUTHOR = {B{ü}rgisser, Peter and Cucker, Felipe},
      TITLE = {Smoothed analysis of {M}oore-{P}enrose inversion},
      JOURNAL = {SIAM J. Matrix Anal. Appl.},
      FJOURNAL = {SIAM Journal on Matrix Analysis and Applications},
      VOLUME = {31},
      YEAR = {2010},
      NUMBER = {5},
      PAGES = {2769--2783},
      ISSN = {0895-4798},
      MRCLASS = {15A09 (65F35)},
      MRNUMBER = {2740632},
      DOI = {10.1137/100782954},
      }
  • [BCL:06a] Go to document P. Bürgisser, F. Cucker, and M. Lotz, "Smoothed analysis of complex conic condition numbers," J. Math. Pures Appl., vol. 86, iss. 4, pp. 293-309, 2006.
    @article {BCL:06a, MRKEY = {2257845},
      AUTHOR = {B{ü}rgisser, Peter and Cucker, Felipe and Lotz, Martin},
      TITLE = {Smoothed analysis of complex conic condition numbers},
      JOURNAL = {J. Math. Pures Appl.},
      FJOURNAL = {Journal de Mathématiques Pures et Appliquées. Neuvième Série},
      VOLUME = {86},
      YEAR = {2006},
      NUMBER = {4},
      PAGES = {293--309},
      ISSN = {0021-7824},
      CODEN = {JMPAAM},
      MRCLASS = {65F35 (53C65 65F22)},
      MRNUMBER = {2257845},
      DOI = {10.1016/j.matpur.2006.06.001},
      ZBLNUMBER={1113.65044},
      }
  • [BCL:06c] Go to document P. Bürgisser, F. Cucker, and M. Lotz, "The probability that a slightly perturbed numerical analysis problem is difficult," Math. Comp., vol. 77, iss. 263, pp. 1559-1583, 2008.
    @article {BCL:06c, MRKEY = {2398780},
      AUTHOR = {B{ü}rgisser, Peter and Cucker, Felipe and Lotz, Martin},
      TITLE = {The probability that a slightly perturbed numerical analysis problem is difficult},
      JOURNAL = {Math. Comp.},
      FJOURNAL = {Mathematics of Computation},
      VOLUME = {77},
      YEAR = {2008},
      NUMBER = {263},
      PAGES = {1559--1583},
      ISSN = {0025-5718},
      CODEN = {MCMPAF},
      MRCLASS = {65J05 (68Q25)},
      MRNUMBER = {2398780},
      MRREVIEWER = {Richard A. Al{ò}},
      DOI = {10.1090/S0025-5718-08-02060-7},
      ZBLNUMBER={1195.65018},
      }
  • [choi:94] Go to document K. P. Choi, "On the medians of gamma distributions and an equation of Ramanujan," Proc. Amer. Math. Soc., vol. 121, iss. 1, pp. 245-251, 1994.
    @article {choi:94, MRKEY = {1195477},
      AUTHOR = {Choi, K. P.},
      TITLE = {On the medians of gamma distributions and an equation of {R}amanujan},
      JOURNAL = {Proc. Amer. Math. Soc.},
      FJOURNAL = {Proceedings of the American Mathematical Society},
      VOLUME = {121},
      YEAR = {1994},
      NUMBER = {1},
      PAGES = {245--251},
      ISSN = {0002-9939},
      CODEN = {PAMYAR},
      MRCLASS = {62E15 (33B15 41A58)},
      MRNUMBER = {1195477},
      MRREVIEWER = {A. M. Mathai},
      DOI = {10.2307/2160389},
      ZBLNUMBER = {0803.62007},
      }
  • [CDW:05] Go to document F. Cucker, H. Diao, and Y. Wei, "Smoothed analysis of some condition numbers," Numer. Linear Algebra Appl., vol. 13, iss. 1, pp. 71-84, 2006.
    @article {CDW:05, MRKEY = {2194973},
      AUTHOR = {Cucker, Felipe and Diao, H. and Wei, Y.},
      TITLE = {Smoothed analysis of some condition numbers},
      JOURNAL = {Numer. Linear Algebra Appl.},
      FJOURNAL = {Numerical Linear Algebra with Applications},
      VOLUME = {13},
      YEAR = {2006},
      NUMBER = {1},
      PAGES = {71--84},
      ISSN = {1070-5325},
      CODEN = {NLAAEM},
      MRCLASS = {65F35 (15A09)},
      MRNUMBER = {2194973},
      MRREVIEWER = {Maria C. Adam},
      DOI = {10.1002/nla.464},
      ZBLNUMBER = {1198.65084},
      }
  • [CuHaLo:08] Go to document F. Cucker, R. Hauser, and M. Lotz, "Adversarial smoothed analysis," J. Complexity, vol. 26, iss. 3, pp. 255-262, 2010.
    @article {CuHaLo:08, MRKEY = {2657364},
      AUTHOR = {Cucker, Felipe and Hauser, Raphael and Lotz, Martin},
      TITLE = {Adversarial smoothed analysis},
      JOURNAL = {J. Complexity},
      FJOURNAL = {Journal of Complexity},
      VOLUME = {26},
      YEAR = {2010},
      NUMBER = {3},
      PAGES = {255--262},
      ISSN = {0885-064X},
      MRCLASS = {15B52 (15A12)},
      MRNUMBER = {2657364},
      DOI = {10.1016/j.jco.2009.12.005},
      ZBLNUMBER = {05763691},
      }
  • [howa:93] R. Howard, "The kinematic formula in Riemannian homogeneous spaces," Mem. Amer. Math. Soc., vol. 106, iss. 509, p. vi, 1993.
    @article {howa:93, MRKEY = {1169230},
      AUTHOR = {Howard, Ralph},
      TITLE = {The kinematic formula in {R}iemannian homogeneous spaces},
      JOURNAL = {Mem. Amer. Math. Soc.},
      FJOURNAL = {Memoirs of the American Mathematical Society},
      VOLUME = {106},
      YEAR = {1993},
      NUMBER = {509},
      PAGES = {vi+69},
      ISSN = {0065-9266},
      CODEN = {MAMCAU},
      MRCLASS = {53C65},
      MRNUMBER = {1169230},
      MRREVIEWER = {L. A. Santal{ó}},
      ZBLNUMBER={0810.53057},
      }
  • [Rabin:80] Go to document M. O. Rabin, "Probabilistic algorithm for testing primality," J. Number Theory, vol. 12, iss. 1, pp. 128-138, 1980.
    @article {Rabin:80, MRKEY = {0566880},
      AUTHOR = {Rabin, Michael O.},
      TITLE = {Probabilistic algorithm for testing primality},
      JOURNAL = {J. Number Theory},
      FJOURNAL = {Journal of Number Theory},
      VOLUME = {12},
      YEAR = {1980},
      NUMBER = {1},
      PAGES = {128--138},
      ISSN = {0022-314X},
      CODEN = {JNUTA9},
      MRCLASS = {10-04 (10A25)},
      MRNUMBER = {0566880},
      MRREVIEWER = {D. H. Lehmer},
      DOI = {10.1016/0022-314X(80)90084-0},
      ZBLNUMBER = {0426.10006},
      }
  • [rene:89] Go to document J. Renegar, "On the worst-case arithmetic complexity of approximating zeros of systems of polynomials," SIAM J. Comput., vol. 18, iss. 2, pp. 350-370, 1989.
    @article {rene:89, MRKEY = {0986672},
      AUTHOR = {Renegar, James},
      TITLE = {On the worst-case arithmetic complexity of approximating zeros of systems of polynomials},
      JOURNAL = {SIAM J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {18},
      YEAR = {1989},
      NUMBER = {2},
      PAGES = {350--370},
      ISSN = {0097-5397},
      CODEN = {SMJCAT},
      MRCLASS = {68Q25 (12-04 12D10 65E05 65H05 90C30)},
      MRNUMBER = {0986672},
      MRREVIEWER = {Josef Wichmann},
      DOI = {10.1137/0218024},
      ZBLNUMBER = {0676.65045},
      }
  • [sast:03] Go to document A. Sankar, D. A. Spielman, and S. Teng, "Smoothed analysis of the condition numbers and growth factors of matrices," SIAM J. Matrix Anal. Appl., vol. 28, iss. 2, pp. 446-476, 2006.
    @article {sast:03, MRKEY = {2255338},
      AUTHOR = {Sankar, Arvind and Spielman, Daniel A. and Teng, Shang-Hua},
      TITLE = {Smoothed analysis of the condition numbers and growth factors of matrices},
      JOURNAL = {SIAM J. Matrix Anal. Appl.},
      FJOURNAL = {SIAM Journal on Matrix Analysis and Applications},
      VOLUME = {28},
      YEAR = {2006},
      NUMBER = {2},
      PAGES = {446--476},
      ISSN = {0895-4798},
      MRCLASS = {65F35 (15A12)},
      MRNUMBER = {2255338},
      MRREVIEWER = {Maria C. Adam},
      DOI = {10.1137/S0895479803436202},
      ZBLNUMBER = {1179.65033},
      }
  • [Shub93b] M. Shub, "Some remarks on Bezout’s theorem and complexity theory," in From Topology to Computation: Proceedings of the Smalefest, New York: Springer-Verlag, 1993, pp. 443-455.
    @incollection {Shub93b, MRKEY = {1246139},
      AUTHOR = {Shub, Michael},
      TITLE = {Some remarks on {B}ezout's theorem and complexity theory},
      BOOKTITLE = {From {T}opology to {C}omputation: {P}roceedings of the {S}malefest},
      VENUE={{B}erkeley, {CA},
      1990},
      PAGES = {443--455},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1993},
      MRCLASS = {14C17 (12D10 14Q20 65H20 68Q25)},
      MRNUMBER = {1246139},
      MRREVIEWER = {Henri Lombardi},
      ZBLNUMBER = {0811.13021},
      }
  • [Bez6] Go to document M. Shub, "Complexity of Bezout’s theorem. VI. Geodesics in the condition (number) metric," Found. Comput. Math., vol. 9, iss. 2, pp. 171-178, 2009.
    @article {Bez6, MRKEY = {2496558},
      AUTHOR = {Shub, Michael},
      TITLE = {Complexity of {B}ezout's theorem. {VI}. {G}eodesics in the condition (number) metric},
      JOURNAL = {Found. Comput. Math.},
      FJOURNAL = {Foundations of Computational Mathematics. The Journal of the Society for the Foundations of Computational Mathematics},
      VOLUME = {9},
      YEAR = {2009},
      NUMBER = {2},
      PAGES = {171--178},
      ISSN = {1615-3375},
      MRCLASS = {65H10 (68Q25)},
      MRNUMBER = {2496558},
      MRREVIEWER = {Guillermo Matera},
      DOI = {10.1007/s10208-007-9017-6},
      }
  • [Bez1] Go to document M. Shub and S. Smale, "Complexity of Bézout’s theorem. I. Geometric aspects," J. Amer. Math. Soc., vol. 6, iss. 2, pp. 459-501, 1993.
    @article {Bez1, MRKEY = {1175980},
      AUTHOR = {Shub, Michael and Smale, Steve},
      TITLE = {Complexity of {B}ézout's theorem. {I}. {G}eometric aspects},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {6},
      YEAR = {1993},
      NUMBER = {2},
      PAGES = {459--501},
      ISSN = {0894-0347},
      MRCLASS = {65H20 (58F14)},
      MRNUMBER = {1175980},
      MRREVIEWER = {Gerd P{ö}nisch},
      DOI = {10.2307/2152805},
      ZBLNUMBER={0821.65035},
      }
  • [Bez2] Go to document M. Shub and S. Smale, "Complexity of Bezout’s theorem. II. Volumes and probabilities," in Computational Algebraic Geometry, Boston, MA: Birkhäuser, 1993, vol. 109, pp. 267-285.
    @incollection {Bez2, MRKEY = {1230872},
      AUTHOR = {Shub, Michael and Smale, Steve},
      TITLE = {Complexity of {B}ezout's theorem. {II}. {V}olumes and probabilities},
      BOOKTITLE = {Computational Algebraic Geometry},
      VENUE={{N}ice, 1992},
      SERIES = {Progr. Math.},
      VOLUME = {109},
      PAGES = {267--285},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston, MA},
      YEAR = {1993},
      MRCLASS = {68Q25 (52A38 52A40 65H20)},
      MRNUMBER = {1230872},
      MRREVIEWER = {Gerd P{ö}nisch},
      DOI={10.1006/jcom.1993.1002},
      ZBLNUMBER={0851.65031},
     }
  • [Bez3] Go to document M. Shub and S. Smale, "Complexity of Bezout’s theorem. III. Condition number and packing," J. Complexity, vol. 9, iss. 1, pp. 4-14, 1993.
    @article {Bez3, MRKEY = {1213484},
      AUTHOR = {Shub, Michael and Smale, Steve},
      TITLE = {Complexity of {B}ezout's theorem. {III}. {C}ondition number and packing},
      JOURNAL = {J. Complexity},
      FJOURNAL = {Journal of Complexity},
      VOLUME = {9},
      YEAR = {1993},
      NUMBER = {1},
      PAGES = {4--14},
      ISSN = {0885-064X},
      MRCLASS = {65Y20 (65H05)},
      MRNUMBER = {1213484},
      MRREVIEWER = {Gerd P{ö}nisch},
      DOI = {10.1006/jcom.1993.1002},
      ZBLNUMBER={0846.65018},
      }
  • [Bez4] Go to document M. Shub and S. Smale, "Complexity of Bezout’s theorem. IV. Probability of success; extensions," SIAM J. Numer. Anal., vol. 33, iss. 1, pp. 128-148, 1996.
    @article {Bez4, MRKEY = {1377247},
      AUTHOR = {Shub, Michael and Smale, Steve},
      TITLE = {Complexity of {B}ezout's theorem. {IV}. {P}robability of success; extensions},
      JOURNAL = {SIAM J. Numer. Anal.},
      FJOURNAL = {SIAM Journal on Numerical Analysis},
      VOLUME = {33},
      YEAR = {1996},
      NUMBER = {1},
      PAGES = {128--148},
      ISSN = {0036-1429},
      CODEN = {SJNAAM},
      MRCLASS = {65Y20 (65H10 65H20 68Q25)},
      MRNUMBER = {1377247},
      MRREVIEWER = {Gerd P{ö}nisch},
      DOI = {10.1137/0733008},
      ZBLNUMBER={0843.65035},
      }
  • [Bez5] Go to document M. Shub and S. Smale, "Complexity of Bezout’s theorem. V. Polynomial time," Theoret. Comput. Sci., vol. 133, iss. 1, pp. 141-164, 1994.
    @article {Bez5, MRKEY = {1294430},
      AUTHOR = {Shub, Michael and Smale, Steve},
      TITLE = {Complexity of {B}ezout's theorem. {V}. {P}olynomial time},
      JOURNAL = {Theoret. Comput. Sci.},
      FJOURNAL = {Theoretical Computer Science},
      VOLUME = {133},
      YEAR = {1994},
      NUMBER = {1},
      PAGES = {141--164},
      ISSN = {0304-3975},
      CODEN = {TCSDI},
      MRCLASS = {65H20 (58F14 65H05 65Y20)},
      MRNUMBER = {1294430},
      MRREVIEWER = {Gerd P{ö}nisch},
      DOI = {10.1016/0304-3975(94)90122-8},
      ZBLNUMBER = {0846.65022},
      }
  • [Smale86] S. Smale, "Newton’s method estimates from data at one point," in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, New York: Springer-Verlag, 1986, pp. 185-196.
    @incollection {Smale86, MRKEY = {0870648},
      AUTHOR = {Smale, Steve},
      TITLE = {Newton's method estimates from data at one point},
      BOOKTITLE = {The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics},
      VENUE={{L}aramie, {W}yo., 1985},
      PAGES = {185--196},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1986},
      MRCLASS = {65J15 (58C30 90C30)},
      MRNUMBER = {0870648},
      MRREVIEWER = {W. C. Rheinboldt},
      ZBLNUMBER = {0613.65058},
      }
  • [Smale97] S. Smale, "Complexity theory and numerical analysis," in Acta Num., Cambridge: Cambridge Univ. Press, 1997, vol. 6, pp. 523-551.
    @incollection {Smale97, MRKEY = {1489262},
      AUTHOR = {Smale, Steve},
      TITLE = {Complexity theory and numerical analysis},
      BOOKTITLE = {Acta Num.},
      SERIES = {Acta Numer.},
      VOLUME = {6},
      PAGES = {523--551},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1997},
      MRCLASS = {65Y20 (68Q15 68Q25)},
      MRNUMBER = {1489262},
      MRREVIEWER = {Klaus Meer},
      ZBLNUMBER = {0883.65125},
      }
  • [smale:00] S. Smale, "Mathematical problems for the next century," in Mathematics: Frontiers and Perspectives, Providence, RI: Amer. Math. Soc., 2000, pp. 271-294.
    @incollection {smale:00, MRKEY = {1754783},
      AUTHOR = {Smale, Steve},
      TITLE = {Mathematical problems for the next century},
      BOOKTITLE = {Mathematics: Frontiers and Perspectives},
      PAGES = {271--294},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {2000},
      MRCLASS = {00A05 (00-02 01A61 01A67)},
      MRNUMBER = {1754783},
      ZBLNUMBER = {1031.00005},
      }
  • [SoSt:77] Go to document R. Solovay and V. Strassen, "A fast Monte-Carlo test for primality," SIAM J. Comput., vol. 6, iss. 1, pp. 84-85, 1977.
    @article {SoSt:77, MRKEY = {0429721},
      AUTHOR = {Solovay, R. and Strassen, V.},
      TITLE = {A fast {M}onte-{C}arlo test for primality},
      JOURNAL = {SIAM J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {6},
      YEAR = {1977},
      NUMBER = {1},
      PAGES = {84--85},
      ISSN = {0097-5397},
      MRCLASS = {10A25 (10-04)},
      MRNUMBER = {0429721},
      MRREVIEWER = {George Marsaglia},
      DOI = {10.1137/0206006},
      ZBLNUMBER = {0345.10002},
      }
  • [ST:02] D. A. Spielman and S. Teng, "Smoothed analysis of algorithms," in Proceedings of the International Congress of Mathematicians, Vol. I, Beijing, 2002, pp. 597-606.
    @inproceedings {ST:02, MRKEY = {1989210},
      AUTHOR = {Spielman, Daniel A. and Teng, Shang-Hua},
      TITLE = {Smoothed analysis of algorithms},
      BOOKTITLE = {Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. {I}},
      VENUE={{B}eijing, 2002},
      PAGES = {597--606},
      PUBLISHER = {Higher Ed. Press},
      ADDRESS = {Beijing},
      YEAR = {2002},
      MRCLASS = {90C60 (68Q25 68W40 90C51)},
      MRNUMBER = {1989210},
      MRREVIEWER = {K. G. Murty},
      ZBLNUMBER = {1056.65148},
      }
  • [ST:04] Go to document D. A. Spielman and S. Teng, "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time," J. ACM, vol. 51, iss. 3, pp. 385-463, 2004.
    @article {ST:04, MRKEY = {2145860},
      AUTHOR = {Spielman, Daniel A. and Teng, Shang-Hua},
      TITLE = {Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time},
      JOURNAL = {J. ACM},
      FJOURNAL = {Journal of the ACM},
      VOLUME = {51},
      YEAR = {2004},
      NUMBER = {3},
      PAGES = {385--463},
      ISSN = {0004-5411},
      MRCLASS = {90C05 (68W40 90C60)},
      MRNUMBER = {2145860},
      MRREVIEWER = {Panos M. Pardalos},
      DOI = {10.1145/990308.990310},
      ZBLNUMBER = {0563.03027},
      }
  • [Wsch:04] Go to document M. Wschebor, "Smoothed analysis of $\kappa(A)$," J. Complexity, vol. 20, iss. 1, pp. 97-107, 2004.
    @article {Wsch:04, MRKEY = {2031560},
      AUTHOR = {Wschebor, Mario},
      TITLE = {Smoothed analysis of {$\kappa(A)$}},
      JOURNAL = {J. Complexity},
      FJOURNAL = {Journal of Complexity},
      VOLUME = {20},
      YEAR = {2004},
      NUMBER = {1},
      PAGES = {97--107},
      ISSN = {0885-064X},
      MRCLASS = {15A52 (15A12 60G15 60G60 65F35)},
      MRNUMBER = {2031560},
      DOI = {10.1016/j.jco.2003.09.003},
      ZBLNUMBER = {1065.15029},
      }

Authors

Peter Bürgisser

Institute of Mathematics
University of Paderborn
D-33098 Paderborn
Germany

Felipe Cucker

Department of Mathematics
City University of Hong Kong
Kowloon Tong
Hong Kong