Linear Equations, Arithmetic Progressions and Hypergraph Property Testing

by Noga Alon and Asaf Shapira

Theory of Computing, Volume 1(9), pp. 177-216, 2005

Bibliography with links to cited articles

[1]   N. Alon: Testing subgraphs in large graphs. Random Structures and Algorithms, 21:359–370, 2002. Also, Proc. 42nd IEEE FOCS, IEEE (2001), 434–441. [FOCS:10.1109/SFCS.2001.959918, RSA:10.1002/rsa.10056].

[2]   N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster: The algorithmic aspects of the regularity lemma. J. of Algorithms, 16:80–109, 1994. Also, Proc. 33rd IEEE FOCS, Pittsburgh, IEEE (1992), 473-481. [FOCS:10.1109/SFCS.1992.267804, JAlg:10.1006/jagm.1994.1005].

[3]   N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy: Efficient testing of large graphs. Combinatorica, 20:451–476, 2000. Also, Proc. of 40th FOCS, New York, NY, IEEE (1999), 656–666. [Combinatorica:mwapje2fdyk7ma2e].

[4]   N. Alon and A. Shapira: A characterization of easily testable induced subgraphs. In Proc. of the 15th Annual ACM-SIAM SODA, pp. 935–944. ACM Press, 2004. Combinatorics, Probability and Computing, to appear.

[5]   N. Alon and A. Shapira: Testing subgraphs in directed graphs. JCSS, 69:354–382, 2004. Also, Proc. of the 35th STOC, 2003, 700–709. [STOC:780542.780644, JCSS:10.1016/j.jcss.2004.04.008].

[6]   N. Alon and A. Shapira: On an extremal hypergraph problem of Brown, Erd~o s and Sós. Combinatorica, to appear, 2005.

[7]   F. A. Behrend: On sets of integers which contain no three terms in arithmetic progression. Proc. of National Academy of Sciences USA, 32:331–332, 1946.

[8]   J. Bourgain: On triples in arithmetic progression. Geom. and Funct. Anal., 9:968–984, 1999. [GAFA:7wqhpp8fnnuk388g].

[9]   P. Erd~o s, P. Frankl, and V. Rödl: The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs and Combin., 2:113–121, 1986.

[10]   P. Erd~o s and M. Simonovits: Supersaturated graphs and hypergraphs. Combinatorica, 3:181–192, 1983.

[11]   E. Fischer: The art of uninformed decisions: A primer to property testing. The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science, 75:97–126, 2001.

[12]   P. Frankl and V. Rödl: Extremal problems on set systems. Random Struct. Algorithms, 20:131–164, 2002. [RSA:10.1002/rsa.10017].

[13]   O. Goldreich, S. Goldwasser, and D. Ron: Property testing and its connection to learning and approximation. JACM, 45:653–750, 1998. Also, Proc. of 37th Annual IEEE FOCS, (1996), 339–348. [FOCS:10.1109/SFCS.1996.548493, JACM:10.1145/285055.285060].

[14]   O. Goldreich and L. Trevisan: Three theorems regarding testing graph properties. Random Structures and Algorithms, 23:23–57, 2003. Also, Proc. 42nd IEEE FOCS, IEEE (2001), 460-469. [FOCS:10.1109/SFCS.2001.959922, RSA:10.1002/rsa.10078].

[15]   W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi theorem. Manuscript, 2004.

[16]   I. S. Gradshteyn and I. M. Ryzhik: Tables of Integrals, Series, and Products. Academic Press, 2000.

[17]   Y. Kohayakawa, B. Nagle, and V. Rödl: Efficient testing of hypergraphs. In Proc. of 29th ICALP, pp. 1017–1028, 2002. [ICALP:4wa2tdcqx50avb08].

[18]   I. Laba and M. Lacey: On sets of integers not containing long arithmetic progressions. Manuscript, 2004. [arXiv:math/0108155].

[19]   B. Nagle and V. Rödl: Regularity properties for triple systems. Random Structures and Algorithms, 23:264–332, 2003. [RSA:10.1002/rsa.10094].

[20]   B. Nagle, V. Rödl, and M. Schacht: The counting lemma for regular k-uniform hypegraphs. Random Structures and Algorithms, to appear.

[21]   R. A. Rankin: Sets of integers containing not more than a given number of terms in arithmetical progression. Proc. Roy. Soc. Edinburgh Sect. A, 65:332–344, 1962.

[22]   V. Rödl and J. Skokan: Regularity lemma for k-uniform hypergraphs. Random Structures and Algorithms, 25:1–42, 2004. [RSA:10.1002/rsa.20017].

[23]   D. Ron: Property testing. Handbook of Randomized Computing, 2:597–649, 2001.

[24]   R. Rubinfeld and M. Sudan: Robust characterization of polynomials with applications to program testing. SIAM J. on Computing, 25:252–271, 1996. [SICOMP:10.1137/S0097539793255151].

[25]   I. Z. Ruzsa and E. Szemerédi: Triple systems with no six points carrying three triangles. In Combinatorics (Keszthely, 1976), pp. 939–945. Coll. Math. Soc. J. Bolyai, 1976.

[26]   A. Shapira: Behrend-type constructions for sets of linear equations. Acta Arithmetica, to appear.

[27]   E. Szemerédi: Regular partitions of graphs. In Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.), pp. 399–401, 1978.