%% v001/a009.bib October 12, 2005 @article{Al, title="Testing subgraphs in large graphs", author="N.~Alon", journal="Random Structures and Algorithms", volume=21, pages="359--370", year=2002, note="Also, Proc. $42^{nd}$ {IEEE} {FOCS}, {IEEE} (2001), 434--441", pdf="http://www.cs.tau.ac.il/~nogaa/PDFS/testsubproc.pdf", eprint={focs:10.1109/SFCS.2001.959918,rsa:10.1002/rsa.10056} } @article{ADLRY, title="The algorithmic aspects of the regularity lemma", author="N. Alon and R. A. Duke and H. Lefmann and V. {R\"{o}dl} and R. Yuster", journal="J. of Algorithms", volume=16, pages="80--109", year=1994, note="Also, Proc. $33^{rd}$ {IEEE} {FOCS}, Pittsburgh, {IEEE} (1992), 473-481", pdf="http://www.cs.tau.ac.il/~nogaa/PDFS/reg5.pdf", eprint={focs:10.1109/SFCS.1992.267804,jalg:10.1006/jagm.1994.1005} } @article{AFKS, title="Efficient testing of large graphs", author="N. Alon and E. Fischer and M. Krivelevich and M. Szegedy", journal="Combinatorica", volume=20, pages="451--476", year=2000, note="Also, Proc. of $40^{th}$ FOCS, New York, NY, IEEE (1999), 656--666", pdf="http://www.cs.tau.ac.il/~nogaa/PDFS/testn12.pdf", eprint={combinatorica:mwapje2fdyk7ma2e} } @article{ASSTOC, title="Testing subgraphs in directed graphs", author="N. Alon and A. Shapira", journal="JCSS", volume=69, pages="354--382", year=2004, note="Also, Proc. of the $35^{th}$ STOC, 2003, 700--709", pdf="http://www.cs.tau.ac.il/~nogaa/PDFS/testdig5.pdf", eprint={stoc:780542.780644,jcss:10.1016/j.jcss.2004.04.008} } @inproceedings{ASSODA, title="A characterization of easily testable induced subgraphs", author="N. Alon and A. Shapira", note="Combinatorics, Probability and Computing, to appear", booktitle={Proc. of the $15^{th}$ Annual ACM-SIAM SODA}, pages="935-944", publisher="{ACM} Press", year=2004, pdf="http://www.cs.tau.ac.il/~nogaa/PDFS/testindfull2.pdf", } @unpublished{ASTuran, title="On an extremal hypergraph problem of {Brown}, {Erd{\H o}s} and {S\'os}", author="N. Alon and A. Shapira", note="Combinatorica, to appear", pdf="http://www.cs.tau.ac.il/~nogaa/PDFS/asaferdos4.pdf", year="2005" } @article{Be, title="On sets of integers which contain no three terms in arithmetic progression", author="F.~A.~Behrend", journal="Proc. of National Academy of Sciences USA", volume=32, pages="331--332", year=1946 } @article{Bourgain, title="On triples in arithmetic progression", author="J. Bourgain", journal="Geom. and Funct. Anal.", volume=9, pages="968--984", year=1999, eprint={GAFA:7wqhpp8fnnuk388g} } @article{EFR, title="The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent", author="P. Erd\H{o}s and P. Frankl and V. R{\"{o}}dl", journal="Graphs and Combin.", volume=2, pages="113--121", year="1986" } @article{ES, title="Supersaturated graphs and hypergraphs", author="P. Erd\H{o}s and M. Simonovits", journal="Combinatorica", volume=3, pages="181--192", year="1983" } @article{F, title="The art of uninformed decisions: A primer to property testing", author="E. Fischer", journal="The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science", volume=75, pages="97--126", year="2001" } @article{FR, title="Extremal problems on set systems", author="P.~{Frankl} and V.~{R{\"{o}}dl}", journal="Random Struct. Algorithms", volume=20, pages="131--164", year="2002", eprint={rsa:10.1002/rsa.10017} } @article{GGR, title="Property testing and its connection to learning and approximation", author="O.~Goldreich and S.~Goldwasser and D.~Ron", journal="JACM", volume=45, pages="653--750", year=1998, note="Also, Proc. of $37^{th}$ Annual IEEE FOCS, (1996), 339--348", eprint={focs:10.1109/SFCS.1996.548493,jacm:10.1145/285055.285060} } @article{GT, title="Three theorems regarding testing graph properties", author="O. Goldreich and L. Trevisan", journal="Random Structures and Algorithms", volume=23, pages="23--57", year="2003", note="Also, Proc. $42^{nd}$ {IEEE} {FOCS}, {IEEE} (2001), 460-469.", eprint={focs:10.1109/SFCS.2001.959922,rsa:10.1002/rsa.10078} } @book{GR, author = {I. S. Gradshteyn and I. M. Ryzhik}, title = {Tables of Integrals, Series, and Products}, publisher = {Academic Press}, year = {2000} } @unpublished{G2, title="Hypergraph regularity and the multidimensional {Szemer\'edi} theorem", author="{W. T.} Gowers", note="Manuscript", year=2004 } @inproceedings{KNR, title="Efficient testing of hypergraphs", author="Y. Kohayakawa and B. Nagle and V. R{\"{o}}dl", booktitle="Proc. of $29^{th}$ ICALP", pages="1017--1028", year=2002, eprint={icalp:4wa2tdcqx50avb08} } @unpublished{LL, title="On sets of integers not containing long arithmetic progressions", author="I. Laba and M. Lacey", note="Manuscript", year="2004", pdf="http://www.arxiv.org/PS_cache/math/pdf/0108/0108155.pdf", eprint={arxiv:math/0108155} } @article{NR, title="Regularity properties for triple systems", author="B. Nagle and V. R{\"{o}}dl", journal="Random Structures and Algorithms", volume=23, pages="264--332", year=2003, eprint={rsa:10.1002/rsa.10094} } @unpublished{NR2, title="The counting lemma for regular $k$-uniform hypegraphs", author="B. Nagle and V. R{\"{o}}dl and M. Schacht", note="Random Structures and Algorithms, to appear", } @article{Rankin, title="Sets of integers containing not more than a given number of terms in arithmetical progression", author="R. A. Rankin", journal="Proc. Roy. Soc. Edinburgh Sect. A", volume=65, pages="332--344", year=1962 } @article{RSk, title="Regularity lemma for $k$-uniform hypergraphs", author="V. R{\"{o}}dl and J. Skokan", journal="Random Structures and Algorithms", volume=25, pages="1--42", year=2004, eprint={rsa:10.1002/rsa.20017} } @article{Ron, title="Property testing", author="D. Ron", journal="Handbook of Randomized Computing", volume=2, pages="597--649", year=2001 } @article{RS, title="Robust characterization of polynomials with applications to program testing", author="R.~Rubinfeld and M.~Sudan", journal="{SIAM} J. on Computing", volume=25, pages="252--271", year=1996, eprint={sicomp:10.1137/S0097539793255151} } @inproceedings{RUSZ, title="Triple systems with no six points carrying three triangles", author="I. Z. Ruzsa and E.~{Szemer\'edi}", booktitle="Combinatorics (Keszthely, 1976)", year=1976, publisher="Coll. Math. Soc. J. Bolyai", pages="939--945" } @unpublished{Sh, title="Behrend-type constructions for sets of linear equations", author="A. Shapira", note="Acta Arithmetica, to appear", pdf="http://www.cs.tau.ac.il/~asafico/behrend.pdf" } @inproceedings{Sz, title="Regular partitions of graphs", author="E.~Szemer\'edi", booktitle="Proc. Colloque Inter. CNRS (J.~C.~Bermond, J.~C.~Fournier, M.~Las~Vergnas and D.~Sotteau, eds.)", pages="399--401", year=1978, }