Algorithmic Aspects of Regularity

1. Alon, N., Duke, R.A., Lefmann, H., Rödl, 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–481. IEEE Comput. Soc. Press, Los Alamitos (1992)

   Chapter  MATH  Google Scholar 

2. Alon, N., Duke, R.A., Lefmann, H., Rödl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. Journal of Algorithms 16(1), 80–109 (1994)

   Article  MathSciNet  MATH  Google Scholar 

3. Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs, p. 22 (1999) (submitted)

   Google Scholar 

4. 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–666. IEEE Comput. Soc. Press, Los Alamitos (1999)

   Google Scholar 

5. Alon, N., Fischer, E.: Refining the graph density condition for the existence of almost K-factors. Ars Combinatoria 52, 296–308 (1999)

   MathSciNet  MATH  Google Scholar 

6. Alon, N., Yuster, R.: Almost H-factors in dense graphs. Graphs and Combinatorics 8(2), 95–102 (1992)

   Article  MathSciNet  MATH  Google Scholar 

7. Alon, N., Yuster, R.: H-factors in dense graphs. Journal of Combinatorial Theory, Series B 66(2), 269–282 (1996)

   Article  MathSciNet  MATH  Google Scholar 

8. Chung, F.R.K.: Regularity lemmas for hypergraphs and quasi-randomness. Random Structures and Algorithms 2(1), 241–252 (1991)

   MathSciNet  MATH  Google Scholar 

9. Chung, F.R.K., Graham, R.L., Wilson, R.M.: Quasi-random graphs. Combinatorica 9(4), 345–362 (1989)

   Article  MathSciNet  MATH  Google Scholar 

10. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9(3), 251–280 (1990)

    Article  MathSciNet  MATH  Google Scholar 

11. Czygrinow, A.: Partitioning problems in dense hypergraphs (1999) (submitted)

    Google Scholar 

12. Czygrinow, A., Poljak, S., Rödl, V.: Constructive quasi-Ramsey numbers and tournament ranking. SIAM Journal on Discrete Mathematics 12(1), 48–63 (1999)

    Article  MathSciNet  MATH  Google Scholar 

13. Czygrinow, A., Rödl, V.: An algorithmic regularity lemma for hypergraphs (1999) (submitted)

    Google Scholar 

14. Duke, R.A., Lefmann, H., Rödl, V.: A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM Journal on Computing 24(3), 598–620 (1995)

    Article  MathSciNet  MATH  Google Scholar 

15. Duke, R.A., Rödl, V.: On graphs with small subgraphs of large chromatic number. Graphs and Combinatorics 1(1), 91–96 (1985)

    Article  MathSciNet  MATH  Google Scholar 

16. Erdős, P., Spencer, J.: Probabilistic methods in combinatorics, p. 106. Akademiai Kiado, Budapest (1974)

    MATH  Google Scholar 

17. Fischer, E.: Cycle factors in dense graphs. Discrete Mathematics 197/198, 309–323 (1999); 16th British Combinatorial Conference (London, 1997)

    Article  MathSciNet  MATH  Google Scholar 

18. Frankl, P., Rödl, V.: Extremal problems on set systems. Random Structures and Algorithms (to appear)

    Google Scholar 

19. Frankl, P., Rödl, V.: The uniformity lemma for hypergraphs. Graphs and Combinatorics 8(4), 309–312 (1992)

    Article  MathSciNet  MATH  Google Scholar 

20. Frankl, P., Rödl, 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 44(3), 317–328 (1988)

    Article  MathSciNet  MATH  Google Scholar 

21. 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–20. IEEE Comput. Soc. Press, Los Alamitos (1996)

    Google Scholar 

22. Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19(2), 175–220 (1999)

    Article  MathSciNet  MATH  Google Scholar 

23. Frieze, A., Kannan, R.: A simple algorithm for constructing Szemerédi’s regularity partition. Electronic Journal of Combinatorics 6(1), 7 (1999) (electronic)

    MATH  Google Scholar 

24. Goldreich, O.: Combinatorial property testing (a survey). Randomization methods in algorithm design, Princeton, NJ (1997); Amer. Math. Soc., Providence, RI, pp. 45–59 (1999)

    Google Scholar 

25. 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–348. IEEE Comput. Soc. Press, Los Alamitos (1996)

    Google Scholar 

26. Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the Association for Computing Machinery 45(4), 653–750 (1998)

    Article  MathSciNet  MATH  Google Scholar 

27. Goldreich, O., Ron, D.: Property testing in bounded degree graphs. In: 29th ACM Symposium on Theory of Computing, El Paso, Texas, pp. 406–419 (1997)

    Google Scholar 

28. Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999)

    Article  MathSciNet  MATH  Google Scholar 

29. Golub, G.H., van Loan, C.F.: Matrix computations. Johns Hopkins University Press, London (1989)

    MATH  Google Scholar 

30. Gowers, W.T.: Lower bounds of tower type for Szemerédi’s uniformity lemma. Geometric and Functional Analysis 7(2), 322–337 (1997)

    Article  MathSciNet  MATH  Google Scholar 

31. Haxell, P.E., Kohayakawa, Y., Luczak, T.: The induced size-Ramsey number of cycles. Combinatorics, Probability, and Computing 4(3), 217–239 (1995)

    Article  MathSciNet  MATH  Google Scholar 

32. Haxell, P.E., Rödl, V.: Integer and fractional packings in dense graphs (1999) (submitted)

    Google Scholar 

33. Kohayakawa, Y.: Szemerédi’s regularity lemma for sparse graphs. In: Cucker, F., Shub, M. (eds.) Foundations of Computational Mathematics, pp. 216–230. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

34. Kohayakawa, Y., Rödl, V., Thoma, L.: An optimal deterministic algorithm for Szemerédi’s regularity lemma (2000) (submitted)

    Google Scholar 

35. Komlós, J., Simonovits, M.: Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics—Paul Erdős is eighty, Keszthely, vol. 2 (1993); Miklós, D., Sós, V.T., Szőnyi, T. (eds.) Bolyai Society Mathematical Studies, vol. 2, pp. 295–352. János Bolyai Mathematical Society, Budapest (1996)

    Google Scholar 

36. Komlós, J.: The blow-up lemma, Combinatorics. Probability and Computing 8(1-2), 161–176 (1999); Recent trends in combinatorics, Mátraháza (1995)

    Article  MathSciNet  MATH  Google Scholar 

37. Komlós, J., Sárközy, G.N., Szemerédi, E.: Blow-up lemma. Combinatorica 17(1), 109–123 (1997)

    Article  MathSciNet  MATH  Google Scholar 

38. Komlós, J., Sárközy, G.N., Szemerédi, E.: An algorithmic version of the blow-up lemma. Random Structures and Algorithms 12(3), 297–312 (1998)

    Article  MathSciNet  MATH  Google Scholar 

39. Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261–277 (1988)

    Article  MathSciNet  MATH  Google Scholar 

40. Lubotzky, A.: Discrete groups, expanding graphs and invariant measures. Birkhäuser Verlag, Basel (1994); with an appendix by Jonathan D. Rogawski

    Book  MATH  Google Scholar 

41. Margulis, G.A.: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24(1), 51–60 (1988)

    MathSciNet  Google Scholar 

42. Prömel, H.J., Steger, A.: Excluding induced subgraphs III. A general asymptotic. Random Structures and Algorithms 3(1), 19–31 (1992)

    Article  MathSciNet  MATH  Google Scholar 

43. Rödl, V., Ruciński, 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. 1518, pp. 25–34. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

44. Rödl, V., Ruciński, A.: Perfect matchings in ε-regular graphs and the blow-up lemma. Combinatorica 19(3), 437–452 (1999)

    Article  MathSciNet  MATH  Google Scholar 

45. Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)

    Article  MathSciNet  MATH  Google Scholar 

46. Sarnak, P.: Some applications of modular forms. Cambridge University Press, Cambridge (1990)

    Book  MATH  Google Scholar 

47. Szemerédi, E.: On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica 27, 199–245 (1975); collection of articles in memory of Juriĭ Vladimirovič Linnik

    Article  MathSciNet  MATH  Google Scholar 

48. Szemerédi, E.: Regular partitions of graphs, Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay) (1976) (Paris), Colloques Internationaux CNRS, 260, pp. 399–401 (1978)

    Google Scholar 

49. Taraz, A.R.: Szemerédis Regularitätslemma, Diplomarbeit, Universität Bonn, p. 83 (April 1995)

    Google Scholar 

50. Thomason, A.G.: Pseudorandom graphs, Random graphs 1985 (Poznań) (1985); North-Holland Math. Stud., vol. 144, New York, pp. 307–331 North-Holland, Amsterdam (1987)

    Google Scholar 

51. 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. 123, pp. 173–195. Cambridge University Press, Cambridge (1987)

    Google Scholar 

52. Tiskin, A.: Bulk-synchronous parallel multiplication of Boolean matrices. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 494–506. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

Download references