{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:53:29Z","timestamp":1742925209244,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540673064"},{"type":"electronic","value":"9783540464150"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/10719839_1","type":"book-chapter","created":{"date-parts":[[2007,4,11]],"date-time":"2007-04-11T12:13:55Z","timestamp":1176293635000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic Aspects of Regularity"],"prefix":"10.1007","author":[{"given":"Y.","family":"Kohayakawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"R\u00f6dl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,4,12]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1109\/SFCS.1992.267804","volume-title":"33rd Annual Symposium on Foundations of Computer Science","author":"N. Alon","year":"1992","unstructured":"Alon, N., Duke, R.A., Lefmann, H., R\u00f6dl, V., Yuster, R.: The algorithmic aspects of the regularity lemma (extended abstract). In: 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, pp. 473\u2013481. IEEE Comput. Soc. Press, Los Alamitos (1992)"},{"issue":"1","key":"1_CR2","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"16","author":"N. Alon","year":"1994","unstructured":"Alon, N., Duke, R.A., Lefmann, H., R\u00f6dl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. Journal of Algorithms\u00a016(1), 80\u2013109 (1994)","journal-title":"Journal of Algorithms"},{"key":"1_CR3","unstructured":"Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs, p. 22 (1999) (submitted)"},{"key":"1_CR4","first-page":"656","volume-title":"40th Annual Symposium on Foundations of Computer Science","author":"N. Alon","year":"1999","unstructured":"Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs (extended abstract). In: 40th Annual Symposium on Foundations of Computer Science, New York City, NY, pp. 656\u2013666. IEEE Comput. Soc. Press, Los Alamitos (1999)"},{"key":"1_CR5","first-page":"296","volume":"52","author":"N. Alon","year":"1999","unstructured":"Alon, N., Fischer, E.: Refining the graph density condition for the existence of almost K-factors. Ars Combinatoria\u00a052, 296\u2013308 (1999)","journal-title":"Ars Combinatoria"},{"issue":"2","key":"1_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02350627","volume":"8","author":"N. Alon","year":"1992","unstructured":"Alon, N., Yuster, R.: Almost H-factors in dense graphs. Graphs and Combinatorics\u00a08(2), 95\u2013102 (1992)","journal-title":"Graphs and Combinatorics"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1006\/jctb.1996.0020","volume":"66","author":"N. Alon","year":"1996","unstructured":"Alon, N., Yuster, R.: H-factors in dense graphs. Journal of Combinatorial Theory, Series B\u00a066(2), 269\u2013282 (1996)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"1_CR8","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1002\/rsa.3240020208","volume":"2","author":"F.R.K. Chung","year":"1991","unstructured":"Chung, F.R.K.: Regularity lemmas for hypergraphs and quasi-randomness. Random Structures and Algorithms\u00a02(1), 241\u2013252 (1991)","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"1_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02125347","volume":"9","author":"F.R.K. Chung","year":"1989","unstructured":"Chung, F.R.K., Graham, R.L., Wilson, R.M.: Quasi-random graphs. Combinatorica\u00a09(4), 345\u2013362 (1989)","journal-title":"Combinatorica"},{"issue":"3","key":"1_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"1_CR11","unstructured":"Czygrinow, A.: Partitioning problems in dense hypergraphs (1999) (submitted)"},{"issue":"1","key":"1_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0895480197318301","volume":"12","author":"A. Czygrinow","year":"1999","unstructured":"Czygrinow, A., Poljak, S., R\u00f6dl, V.: Constructive quasi-Ramsey numbers and tournament ranking. SIAM Journal on Discrete Mathematics\u00a012(1), 48\u201363 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., R\u00f6dl, V.: An algorithmic regularity lemma for hypergraphs (1999) (submitted)","DOI":"10.1137\/S0097539799351729"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/S0097539793247634","volume":"24","author":"R.A. Duke","year":"1995","unstructured":"Duke, R.A., Lefmann, H., R\u00f6dl, V.: A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM Journal on Computing\u00a024(3), 598\u2013620 (1995)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"1_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02582932","volume":"1","author":"R.A. Duke","year":"1985","unstructured":"Duke, R.A., R\u00f6dl, V.: On graphs with small subgraphs of large chromatic number. Graphs and Combinatorics\u00a01(1), 91\u201396 (1985)","journal-title":"Graphs and Combinatorics"},{"key":"1_CR16","first-page":"106","volume-title":"Probabilistic methods in combinatorics","author":"P. Erd\u0151s","year":"1974","unstructured":"Erd\u0151s, P., Spencer, J.: Probabilistic methods in combinatorics, p. 106. Akademiai Kiado, Budapest (1974)"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0012-365X(98)00242-8","volume":"197","author":"E. Fischer","year":"1999","unstructured":"Fischer, E.: Cycle factors in dense graphs. Discrete Mathematics\u00a0197\/198, 309\u2013323 (1999); 16th British Combinatorial Conference (London, 1997)","journal-title":"Discrete Mathematics"},{"key":"1_CR18","unstructured":"Frankl, P., R\u00f6dl, V.: Extremal problems on set systems. Random Structures and Algorithms (to appear)"},{"issue":"4","key":"1_CR19","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF02351586","volume":"8","author":"P. Frankl","year":"1992","unstructured":"Frankl, P., R\u00f6dl, V.: The uniformity lemma for hypergraphs. Graphs and Combinatorics\u00a08(4), 309\u2013312 (1992)","journal-title":"Graphs and Combinatorics"},{"issue":"3","key":"1_CR20","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0095-8956(88)90040-8","volume":"44","author":"P. Frankl","year":"1988","unstructured":"Frankl, P., R\u00f6dl, V., Wilson, R.M.: The number of submatrices of a given type in a Hadamard matrix and related results. Journal of Combinatorial Theory, Series B\u00a044(3), 317\u2013328 (1988)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1_CR21","first-page":"12","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"A. Frieze","year":"1996","unstructured":"Frieze, A., Kannan, R.: The regularity lemma and approximation schemes for dense problems. In: 37th Annual Symposium on Foundations of Computer Science, Burlington, VT, pp. 12\u201320. IEEE Comput. Soc. Press, Los Alamitos (1996)"},{"issue":"2","key":"1_CR22","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A. Frieze","year":"1999","unstructured":"Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica\u00a019(2), 175\u2013220 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"1_CR23","doi-asserted-by":"crossref","first-page":"7","DOI":"10.37236\/1449","volume":"6","author":"A. Frieze","year":"1999","unstructured":"Frieze, A., Kannan, R.: A simple algorithm for constructing Szemer\u00e9di\u2019s regularity partition. Electronic Journal of Combinatorics\u00a06(1), 7 (1999) (electronic)","journal-title":"Electronic Journal of Combinatorics"},{"key":"#cr-split#-1_CR24.1","unstructured":"Goldreich, O.: Combinatorial property testing (a survey). Randomization methods in algorithm design, Princeton, NJ (1997)"},{"key":"#cr-split#-1_CR24.2","unstructured":"Amer. Math. Soc., Providence, RI, pp. 45-59 (1999)"},{"key":"1_CR25","first-page":"339","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"O. Goldreich","year":"1996","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. In: 37th Annual Symposium on Foundations of Computer Science, Burlington, VT, pp. 339\u2013348. IEEE Comput. Soc. Press, Los Alamitos (1996)"},{"issue":"4","key":"1_CR26","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 Association for Computing Machinery\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. In: 29th ACM Symposium on Theory of Computing, El Paso, Texas, pp. 406\u2013419 (1997)","DOI":"10.1145\/258533.258627"},{"issue":"3","key":"1_CR28","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica\u00a019(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"key":"1_CR29","volume-title":"Matrix computations","author":"G.H. Golub","year":"1989","unstructured":"Golub, G.H., van Loan, C.F.: Matrix computations. Johns Hopkins University Press, London (1989)"},{"issue":"2","key":"1_CR30","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/PL00001621","volume":"7","author":"W.T. Gowers","year":"1997","unstructured":"Gowers, W.T.: Lower bounds of tower type for Szemer\u00e9di\u2019s uniformity lemma. Geometric and Functional Analysis\u00a07(2), 322\u2013337 (1997)","journal-title":"Geometric and Functional Analysis"},{"issue":"3","key":"1_CR31","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1017\/S0963548300001619","volume":"4","author":"P.E. Haxell","year":"1995","unstructured":"Haxell, P.E., Kohayakawa, Y., Luczak, T.: The induced size-Ramsey number of cycles. Combinatorics, Probability, and Computing\u00a04(3), 217\u2013239 (1995)","journal-title":"Combinatorics, Probability, and Computing"},{"key":"1_CR32","unstructured":"Haxell, P.E., R\u00f6dl, V.: Integer and fractional packings in dense graphs (1999) (submitted)"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/978-3-642-60539-0_16","volume-title":"Foundations of Computational Mathematics","author":"Y. Kohayakawa","year":"1997","unstructured":"Kohayakawa, Y.: Szemer\u00e9di\u2019s regularity lemma for sparse graphs. In: Cucker, F., Shub, M. (eds.) Foundations of Computational Mathematics, pp. 216\u2013230. Springer, Heidelberg (1997)"},{"key":"1_CR34","unstructured":"Kohayakawa, Y., R\u00f6dl, V., Thoma, L.: An optimal deterministic algorithm for Szemer\u00e9di\u2019s regularity lemma (2000) (submitted)"},{"key":"#cr-split#-1_CR35.1","unstructured":"Koml\u00f3s, J., Simonovits, M.: Szemer\u00e9di's regularity lemma and its applications in graph theory, Combinatorics-Paul Erd\u0151s is eighty, Keszthely, vol. 2 (1993)"},{"key":"#cr-split#-1_CR35.2","unstructured":"Mikl\u00f3s, D., S\u00f3s, V.T., Sz\u0151nyi, T. (eds.) Bolyai Society Mathematical Studies, vol.\u00a02, pp. 295-352. J\u00e1nos Bolyai Mathematical Society, Budapest (1996)"},{"issue":"1-2","key":"1_CR36","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1017\/S0963548398003502","volume":"8","author":"J. Koml\u00f3s","year":"1999","unstructured":"Koml\u00f3s, J.: The blow-up lemma, Combinatorics. Probability and Computing\u00a08(1-2), 161\u2013176 (1999); Recent trends in combinatorics, M\u00e1trah\u00e1za (1995)","journal-title":"Probability and Computing"},{"issue":"1","key":"1_CR37","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01196135","volume":"17","author":"J. Koml\u00f3s","year":"1997","unstructured":"Koml\u00f3s, J., S\u00e1rk\u00f6zy, G.N., Szemer\u00e9di, E.: Blow-up lemma. Combinatorica\u00a017(1), 109\u2013123 (1997)","journal-title":"Combinatorica"},{"issue":"3","key":"1_CR38","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q","volume":"12","author":"J. Koml\u00f3s","year":"1998","unstructured":"Koml\u00f3s, J., S\u00e1rk\u00f6zy, G.N., Szemer\u00e9di, E.: An algorithmic version of the blow-up lemma. Random Structures and Algorithms\u00a012(3), 297\u2013312 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica\u00a08, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"1_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0346-0332-4","volume-title":"Discrete groups, expanding graphs and invariant measures","author":"A. Lubotzky","year":"1994","unstructured":"Lubotzky, A.: Discrete groups, expanding graphs and invariant measures. Birkh\u00e4user Verlag, Basel (1994); with an appendix by Jonathan D. Rogawski"},{"issue":"1","key":"1_CR41","first-page":"51","volume":"24","author":"G.A. Margulis","year":"1988","unstructured":"Margulis, G.A.: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii\u00a024(1), 51\u201360 (1988)","journal-title":"Problemy Peredachi Informatsii"},{"issue":"1","key":"1_CR42","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/rsa.3240030104","volume":"3","author":"H.J. Pr\u00f6mel","year":"1992","unstructured":"Pr\u00f6mel, H.J., Steger, A.: Excluding induced subgraphs III. A general asymptotic. Random Structures and Algorithms\u00a03(1), 19\u201331 (1992)","journal-title":"Random Structures and Algorithms"},{"key":"1_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-49543-6_3","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"V. R\u00f6dl","year":"1998","unstructured":"R\u00f6dl, V., Ruci\u0144ski, A., Wagner, M.: An algorithmic embedding of graphs via perfect matchings. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol.\u00a01518, pp. 25\u201334. Springer, Heidelberg (1998)"},{"issue":"3","key":"1_CR44","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s004930050063","volume":"19","author":"V. R\u00f6dl","year":"1999","unstructured":"R\u00f6dl, V., Ruci\u0144ski, A.: Perfect matchings in \u03b5-regular graphs and the blow-up lemma. Combinatorica\u00a019(3), 437\u2013452 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"1_CR45","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":"1_CR46","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511895593","volume-title":"Some applications of modular forms","author":"P. Sarnak","year":"1990","unstructured":"Sarnak, P.: Some applications of modular forms. Cambridge University Press, Cambridge (1990)"},{"key":"1_CR47","doi-asserted-by":"publisher","first-page":"199","DOI":"10.4064\/aa-27-1-199-245","volume":"27","author":"E. Szemer\u00e9di","year":"1975","unstructured":"Szemer\u00e9di, E.: On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica\u00a027, 199\u2013245 (1975); collection of articles in memory of Juri\u012d Vladimirovi\u010d Linnik","journal-title":"Acta Arithmetica"},{"key":"1_CR48","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs, Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay) (1976) (Paris), Colloques Internationaux CNRS, 260, pp. 399\u2013401 (1978)"},{"key":"1_CR49","unstructured":"Taraz, A.R.: Szemer\u00e9dis Regularit\u00e4tslemma, Diplomarbeit, Universit\u00e4t Bonn, p. 83 (April 1995)"},{"key":"#cr-split#-1_CR50.1","unstructured":"Thomason, A.G.: Pseudorandom graphs, Random graphs 1985 (Pozna\u0144) (1985)"},{"key":"#cr-split#-1_CR50.2","unstructured":"North-Holland Math. Stud., vol. 144, New York, pp. 307-331 North-Holland, Amsterdam (1987)"},{"key":"1_CR51","series-title":"London Mathematical Society Lecture Note Series","first-page":"173","volume-title":"Surveys in Combinatorics","author":"A.G. Thomason","year":"1987","unstructured":"Thomason, A.G.: Random graphs, strongly regular graphs and pseudorandom graphs. In: Whitehead, C. (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol.\u00a0123, pp. 173\u2013195. Cambridge University Press, Cambridge (1987)"},{"key":"1_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/BFb0055078","volume-title":"Automata, Languages and Programming","author":"A. Tiskin","year":"1998","unstructured":"Tiskin, A.: Bulk-synchronous parallel multiplication of Boolean matrices. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 494\u2013506. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2000: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10719839_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T12:17:56Z","timestamp":1628770676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10719839_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540673064","9783540464150"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/10719839_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"12 April 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}