{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:16Z","timestamp":1725600316480},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_42","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"495-506","source":"Crossref","is-referenced-by-count":0,"title":["A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma"],"prefix":"10.1007","author":[{"given":"Domingos","family":"Dellamonica","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subrahmanyam","family":"Kalyanasundaram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Martin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica\u00a06, 83\u201396 (1986), doi:10.1007\/BF02579166","journal-title":"Combinatorica"},{"key":"42_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. J. Algorithms\u00a016, 80\u2013109 (1994)","journal-title":"J. Algorithms"},{"key":"42_CR3","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1145\/1007352.1007371","volume-title":"Proceedings of the Thirty-Sixth Annual Acm Symposium on Theory of Computing, STOC 1984","author":"N. Alon","year":"2004","unstructured":"Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck\u2019s inequality. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC 1984, pp. 72\u201380. ACM, New York (2004)"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1109\/FOCS.2009.76","volume-title":"Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 745\u2013754. IEEE Computer Society, Washington, DC, USA (2009)"},{"key":"42_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"R. Bhatia","year":"1997","unstructured":"Bhatia, R.: Matrix Analysis. Springer, New York (1997)"},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0211037","volume":"11","author":"D. Coppersmith","year":"1982","unstructured":"Coppersmith, D.: Rapid multiplication of rectangular matrices. SIAM J. Computing\u00a011, 467\u2013471 (1982)","journal-title":"SIAM J. Computing"},{"key":"42_CR7","first-page":"1","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987","author":"D. Coppersmith","year":"1987","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 1\u20136. ACM, New York (1987)"},{"issue":"3","key":"42_CR8","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 J. Comput.\u00a024(3), 598\u2013620 (1995)","journal-title":"SIAM J. Comput."},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Frieze, A., Kannan, R.: The regularity lemma and approximation schemes for dense problems. In: Annual IEEE Symposium on Foundations of Computer Science, p. 12 (1996)","DOI":"10.1109\/SFCS.1996.548459"},{"key":"42_CR10","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, 175\u2013220 (1999)","journal-title":"Combinatorica"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Frieze, A., Kannan, R.: A simple algorithm for constructing Szemer\u00e9di\u2019s regularity partition. Electr. J. Comb. 6 (1999) (electronic)","DOI":"10.37236\/1449"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1017\/S0963548305007236","volume":"15","author":"W.T. Gowers","year":"2006","unstructured":"Gowers, W.T.: Quasirandomness, counting and regularity for 3-uniform hypergraphs. Comb. Probab. Comput.\u00a015, 143\u2013184 (2006)","journal-title":"Comb. Probab. Comput."},{"key":"42_CR13","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, 322\u2013337 (1997)","journal-title":"Geometric And Functional Analysis"},{"key":"42_CR14","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1137\/S0097539702408223","volume":"32","author":"Y. Kohayakawa","year":"2003","unstructured":"Kohayakawa, Y., R\u00f6dl, V., Thoma, L.: An optimal algorithm for checking regularity. SIAM J. Comput.\u00a032, 1210\u20131235 (2003); Earlier verison in SODA 2002","journal-title":"SIAM J. Comput."},{"key":"42_CR15","first-page":"84","volume-title":"The regularity lemma and its applications in graph theory","author":"J. Koml\u00f3s","year":"2002","unstructured":"Koml\u00f3s, J., Shokoufandeh, A., Simonovits, M., Szemer\u00e9di, E.: The regularity lemma and its applications in graph theory, pp. 84\u2013112. Springer-Verlag New York, Inc., New York (2002)"},{"issue":"4","key":"42_CR16","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J. Kuczy\u0144ski","year":"1992","unstructured":"Kuczy\u0144ski, J., Wo\u017aniakowski, H.: Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applications\u00a013(4), 1094\u20131122 (1992)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Very large graphs. In: Jerison, D., Mazur, B., Mrowka, T., Schmid, W., Stanley, R., Yau, S.T. (eds.) Current Developments in Mathematics (2008)","DOI":"10.4310\/CDM.2008.v2008.n1.a2"},{"key":"42_CR18","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1090\/S0025-5718-1979-0537973-X","volume":"33","author":"D.P. O\u2019Leary","year":"1979","unstructured":"O\u2019Leary, D.P., Stewart, G.W., Vandergraft, J.S.: Quasirandomness, counting and regularity for 3-uniform hypergraphs. Mathematics of Computation\u00a033, 1289\u20131292 (1979)","journal-title":"Mathematics of Computation"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"R\u00f6dl, V., Schacht., M.: Regularity lemmas for graphs. In: Fete of Combinatorics and Computer Science. Bolyai Society Mathematical Studies, vol.\u00a020, pp. 287\u2013325. Springer, Heidelberg","DOI":"10.1007\/978-3-642-13580-4_11"},{"key":"42_CR20","first-page":"199","volume":"27","author":"E. Szemer\u00e9di","year":"1975","unstructured":"Szemer\u00e9di, E.: On sets of integers containing no k elements in arithmetic progressions. Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica\u00a027, 199\u2013245 (1975)","journal-title":"Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica"},{"key":"42_CR21","first-page":"399","volume-title":"Probl\u00e9mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)","author":"E. Szemer\u00e9di","year":"1978","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs. In: Probl\u00e9mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 399\u2013401. \u00c9ditions du Centre National de la Recherche Scientifique (CNRS), Paris (1978)"},{"key":"42_CR22","series-title":"Bolyai Society Mathematical Studies","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/978-3-642-14444-8_19","volume-title":"An Irregular Mind","author":"L. Trevisan","year":"2010","unstructured":"Trevisan, L.: Pseudorandomness in computer science and in additive combinatorics. In: An Irregular Mind. Bolyai Society Mathematical Studies, vol.\u00a021, pp. 619\u2013650. Springer, Heidelberg (2010)"},{"key":"42_CR23","unstructured":"Trevisan, L.: Lecture notes, http:\/\/lucatrevisan.wordpress.com\/"},{"key":"42_CR24","doi-asserted-by":"crossref","unstructured":"Williams, R.: Private Communication (2009)","DOI":"10.4324\/9780203874998"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T06:51:31Z","timestamp":1592808691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}