{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:00Z","timestamp":1750694700886,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405450"},{"type":"electronic","value":"9783540450788"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45078-8_23","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T21:23:52Z","timestamp":1277241832000},"page":"256-270","source":"Crossref","is-referenced-by-count":16,"title":["Smoothed Analysis"],"prefix":"10.1007","author":[{"given":"Daniel A.","family":"Spielman","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1109\/SFCS.2000.892111","volume-title":"41st Annual Symposium on Foundations of Computer Science","author":"N. Alon","year":"2000","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of clustering. In: 41st Annual Symposium on Foundations of Computer Science, pp. 240\u2013250. IEEE, Los Alamitos (2000)"},{"key":"23_CR2","first-page":"656","volume-title":"40th Annual Symposium on Foundations of Computer Science","author":"N. Alon","year":"1999","unstructured":"Alon, N., Krivelevich, M., Fischer, E., Szegedy, M.: Efficient testing of large graphs. In: 40th Annual Symposium on Foundations of Computer Science, pp. 656\u2013666. IEEE, Los Alamitos (1999)"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N.: Testing subgraphs in large graphs. In: IEEE (ed.) Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science: proceedings, pp. 434\u2013439 (2001)","DOI":"10.1109\/SFCS.2001.959918"},{"key":"23_CR4","first-page":"905","volume-title":"Proceedings of the 13th Annual ACM SIAM Symposium On Discrete Mathematics (SODA 2002)","author":"A. Blum","year":"2002","unstructured":"Blum, A., Dunagan, J.: Smoothed analysis of the perceptron algorithm for linear programming. In: Proceedings of the 13th Annual ACM SIAM Symposium On Discrete Mathematics (SODA 2002), pp. 905\u2013914. ACM Press, New York (2002)"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-49381-6_15","volume-title":"Algorithms and Computation","author":"P. Bose","year":"1998","unstructured":"Bose, P., Morin, P.: Testing the quality of manufactured disks and cylinders. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol.\u00a01533, pp. 129\u2013138. Springer, Heidelberg (1998)"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Bose, P., Morin, P.: Testing the quality of manufactured balls. In: Workshop on Algorithms and Data Structures, pp. 145\u2013156 (1999)","DOI":"10.1007\/3-540-48447-7_16"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Boppana, R.: Eigenvalues and graph bisection: An average-case analysis. In: Proceedings of the 28th Symposium on Foundation of Computer Science, pp. 280\u2013285 (1987)","DOI":"10.1109\/SFCS.1987.22"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Ron, D.: Testing acyclicity of directed graphs in sublinear time. Automata, Languages and Programming, 809\u2013820 (2000)","DOI":"10.1007\/3-540-45022-X_68"},{"issue":"2","key":"23_CR9","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A. Blum","year":"1995","unstructured":"Blum, A., Spencer, J.: Coloring random and semi-random k-colorable graphs. J. Algorithms\u00a019(2), 204\u2013234 (1995)","journal-title":"J. Algorithms"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-45726-7_12","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"A. Coja-Oghlan","year":"2002","unstructured":"Coja-Oghlan, A.: Finding sparse induced subgraphs of semirandom graphs. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 139\u2013148. Springer, Heidelberg (2002)"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/3-540-44676-1_22","volume-title":"Algorithms - ESA 2001","author":"A. Czumaj","year":"2001","unstructured":"Czumaj, A., Sohler, C.: Property testing with geometric queries. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 266\u2013277. Springer, Heidelberg (2001)"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Abstract combinatorial programs and efficient property testers. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 83\u201392 (2002)","DOI":"10.1109\/SFCS.2002.1181885"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C., Ziegler, M.: Property testing in computational geometry. In: European Symposium on Algorithms, pp. 155\u2013166 (2000)","DOI":"10.1007\/3-540-45253-2_15"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonocity. In: Proceedings of RANDOM, pp. 97\u2013108 (1999)","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"23_CR15","unstructured":"Dunagan, J., Spielman, D.A., Teng, S.-H.: Smoothed analysis of interior point methods: Condition numbers (2002), Available at http:\/\/arxiv.org\/abs\/cs.DS\/0302011"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Ergun, F., Kannan, S., Ravi Kumar, S., Rubinfeld, R., Viswanathan, M.: Spot-checkers. In: ACM Symposium on Theory of Computing, pp. 259\u2013268 (1998)","DOI":"10.1145\/276698.276757"},{"key":"23_CR17","first-page":"674","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Heuristics for finding large independent sets, with applications to coloring semi-random graphs. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 674\u2013683. IEEE, Los Alamitos (1998)"},{"key":"23_CR18","unstructured":"Feige, U., Krauthgamer, R.: Improved performance guarantees for bandwidth minimization heuristics (1998) (unpublished manuscript)"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D.: Testing monotonicity. In: IEEE Symposium on Foundations of Computer Science, pp. 426\u2013435 (1998)","DOI":"10.1109\/SFCS.1998.743493"},{"issue":"4","key":"23_CR20","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 406\u2013415 (1997)","DOI":"10.1145\/258533.258627"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/276698.276767","volume-title":"Proceedings of the thirtieth annual ACM Symposium on Theory of Computing","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. In: ACM (ed.) Proceedings of the thirtieth annual ACM Symposium on Theory of Computing, pp. 289\u2013298. ACM Press, New York (1998)"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 460\u2013469 (2001)","DOI":"10.1109\/SFCS.2001.959922"},{"issue":"3","key":"23_CR24","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1006\/jcss.1999.1656","volume":"61","author":"M. Kearns","year":"2000","unstructured":"Kearns, M., Ron, D.: Testing problems with sublearning sample complexity. J. of Comput. Syst. Sci.\u00a061(3), 428\u2013456 (2000)","journal-title":"J. of Comput. Syst. Sci."},{"key":"23_CR25","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1997","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1997)"},{"key":"23_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-540-48413-4_9","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Parnas","year":"1999","unstructured":"Parnas, M., Ron, D.: Testing the diameter of graphs. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol.\u00a01671, pp. 85\u201396. Springer, Heidelberg (1999)"},{"key":"23_CR27","series-title":"Handbook on Randomized Computing","volume-title":"Property testing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing. Handbook on Randomized Computing, vol.\u00a0II. Kluwer Academic Publishers, Dordrecht (2001)"},{"issue":"2","key":"23_CR28","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001), pp. 296\u2013305 (2001)","DOI":"10.1145\/380752.380813"},{"key":"23_CR30","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms. In: Proceedings of the International Congress of Mathematicians, vol.\u00a01 (2002) (to appear)"},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of termination of linear programming algorithms. Mathematical Programming B (2003) (to appear)","DOI":"10.1007\/s10107-003-0448-9"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45078-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T05:00:30Z","timestamp":1740200430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45078-8_23"}},"subtitle":["Motivation and Discrete Models"],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405450","9783540450788"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45078-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}