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. 781793, 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 = {781793},
ISSN = {0003486X},
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/s101070100346x},
} 
[bast:83] W. Baur and V. Strassen, "The complexity of partial derivatives," Theoret. Comput. Sci., vol. 22, iss. 3, pp. 317330, 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 = {317330},
ISSN = {03043975},
CODEN = {TCSDI},
MRCLASS = {68C25 (1203 12F99)},
MRNUMBER = {0693063},
DOI = {10.1016/03043975(83)90110X},
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. 143, 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 = {143},
ISSN = {16153375},
MRCLASS = {65H10 (68W20)},
MRNUMBER = {2403529},
MRREVIEWER = {Jan M. Verschelde},
DOI = {10.1007/s1020800502110},
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. 363385, 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 = {363385},
ISSN = {08940347},
MRCLASS = {90C30 (14Q20 65H20 68Q25)},
MRNUMBER = {2476778},
MRREVIEWER = {Jan M. Verschelde},
DOI = {10.1090/S0894034708006309},
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. 95129, 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 = {95129},
ISSN = {16153375},
MRCLASS = {65H20 (13P15 65H10 65Y20)},
MRNUMBER = {2754191},
MRREVIEWER = {Mihai Cipu},
DOI = {10.1007/s1020801090789},
} 
[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. 179195, 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 = {179195},
ISSN = {16153375},
MRCLASS = {65H10 (68Q25)},
MRNUMBER = {2496559},
MRREVIEWER = {Guillermo Matera},
DOI = {10.1007/s1020800790185},
} 
[bcss:95] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, New York: SpringerVerlag, 1998.
@book {bcss:95, MRKEY = {1479636},
AUTHOR = {Blum, Lenore and Cucker, Felipe and Shub, Michael and Smale, Steve},
TITLE = {Complexity and Real Computation},
PUBLISHER = {SpringerVerlag},
ADDRESS = {New York},
YEAR = {1998},
PAGES = {xvi+453},
ISBN = {0387982817},
MRCLASS = {68Q15 (03D15 13P99 14P99 65Y20 6802)},
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: NPcompleteness, recursive functions and universal machines," Bull. Amer. Math. Soc., vol. 21, iss. 1, pp. 146, 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 = {146},
ISSN = {02730979},
CODEN = {BAMOAD},
MRCLASS = {68Q10 (03D15 03D75 03D80 03F60 68Q15 68Q25)},
MRNUMBER = {0974426},
MRREVIEWER = {John Michael Robson},
DOI = {10.1090/S027309791989157509},
ZBLNUMBER = {0681.03020},
} 
[BC:10] P. Bürgisser and F. Cucker, "Smoothed analysis of MoorePenrose inversion," SIAM J. Matrix Anal. Appl., vol. 31, iss. 5, pp. 27692783, 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 = {27692783},
ISSN = {08954798},
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. 293309, 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 = {293309},
ISSN = {00217824},
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. 15591583, 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 = {15591583},
ISSN = {00255718},
CODEN = {MCMPAF},
MRCLASS = {65J05 (68Q25)},
MRNUMBER = {2398780},
MRREVIEWER = {Richard A. Al{ò}},
DOI = {10.1090/S0025571808020607},
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. 245251, 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 = {245251},
ISSN = {00029939},
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. 7184, 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 = {7184},
ISSN = {10705325},
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. 255262, 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 = {255262},
ISSN = {0885064X},
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 = {00659266},
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. 128138, 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 = {128138},
ISSN = {0022314X},
CODEN = {JNUTA9},
MRCLASS = {1004 (10A25)},
MRNUMBER = {0566880},
MRREVIEWER = {D. H. Lehmer},
DOI = {10.1016/0022314X(80)900840},
ZBLNUMBER = {0426.10006},
} 
[rene:89] J. Renegar, "On the worstcase arithmetic complexity of approximating zeros of systems of polynomials," SIAM J. Comput., vol. 18, iss. 2, pp. 350370, 1989.
@article {rene:89, MRKEY = {0986672},
AUTHOR = {Renegar, James},
TITLE = {On the worstcase 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 = {350370},
ISSN = {00975397},
CODEN = {SMJCAT},
MRCLASS = {68Q25 (1204 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. 446476, 2006.
@article {sast:03, MRKEY = {2255338},
AUTHOR = {Sankar, Arvind and Spielman, Daniel A. and Teng, ShangHua},
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 = {446476},
ISSN = {08954798},
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: SpringerVerlag, 1993, pp. 443455.
@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 = {443455},
PUBLISHER = {SpringerVerlag},
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. 171178, 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 = {171178},
ISSN = {16153375},
MRCLASS = {65H10 (68Q25)},
MRNUMBER = {2496558},
MRREVIEWER = {Guillermo Matera},
DOI = {10.1007/s1020800790176},
} 
[Bez1] M. Shub and S. Smale, "Complexity of BÃ©zout’s theorem. I. Geometric aspects," J. Amer. Math. Soc., vol. 6, iss. 2, pp. 459501, 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 = {459501},
ISSN = {08940347},
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. 267285.
@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 = {267285},
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. 414, 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 = {414},
ISSN = {0885064X},
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. 128148, 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 = {128148},
ISSN = {00361429},
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. 141164, 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 = {141164},
ISSN = {03043975},
CODEN = {TCSDI},
MRCLASS = {65H20 (58F14 65H05 65Y20)},
MRNUMBER = {1294430},
MRREVIEWER = {Gerd P{ö}nisch},
DOI = {10.1016/03043975(94)901228},
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: SpringerVerlag, 1986, pp. 185196.
@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 = {185196},
PUBLISHER = {SpringerVerlag},
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. 523551.
@incollection {Smale97, MRKEY = {1489262},
AUTHOR = {Smale, Steve},
TITLE = {Complexity theory and numerical analysis},
BOOKTITLE = {Acta Num.},
SERIES = {Acta Numer.},
VOLUME = {6},
PAGES = {523551},
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. 271294.
@incollection {smale:00, MRKEY = {1754783},
AUTHOR = {Smale, Steve},
TITLE = {Mathematical problems for the next century},
BOOKTITLE = {Mathematics: Frontiers and Perspectives},
PAGES = {271294},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
YEAR = {2000},
MRCLASS = {00A05 (0002 01A61 01A67)},
MRNUMBER = {1754783},
ZBLNUMBER = {1031.00005},
} 
[SoSt:77] R. Solovay and V. Strassen, "A fast MonteCarlo test for primality," SIAM J. Comput., vol. 6, iss. 1, pp. 8485, 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 = {8485},
ISSN = {00975397},
MRCLASS = {10A25 (1004)},
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. 597606.
@inproceedings {ST:02, MRKEY = {1989210},
AUTHOR = {Spielman, Daniel A. and Teng, ShangHua},
TITLE = {Smoothed analysis of algorithms},
BOOKTITLE = {Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. {I}},
VENUE={{B}eijing, 2002},
PAGES = {597606},
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. 385463, 2004.
@article {ST:04, MRKEY = {2145860},
AUTHOR = {Spielman, Daniel A. and Teng, ShangHua},
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 = {385463},
ISSN = {00045411},
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. 97107, 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 = {97107},
ISSN = {0885064X},
MRCLASS = {15A52 (15A12 60G15 60G60 65F35)},
MRNUMBER = {2031560},
DOI = {10.1016/j.jco.2003.09.003},
ZBLNUMBER = {1065.15029},
}