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]. [ .pdf ] |
| [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]. [ .pdf ] |
| [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]. [ .pdf ] |
| [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. [ .pdf ] |
| [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]. [ .pdf ] |
| [6] |
N. Alon and A. Shapira: On an extremal hypergraph problem of Brown,
Erd os and Sós.
Combinatorica, to appear, 2005. [ .pdf ] |
| [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. Erdos, 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. Erdos 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]. [ .pdf ] |
| [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. [ .pdf ] |
| [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. |
This file has been generated by bibtex2html 1.74