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
-
[AKS:04]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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},
}