{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T19:23:21Z","timestamp":1791314601745,"version":"4.3.1"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451\u2013476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is $\\epsilon$-testable. However, the complexity of the test is double-tower with respect to $1\/\\epsilon$, as the only tool known to construct such tests uses a variant of Szemer\u00e9di's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is $\\epsilon$-testable, with a number of queries that is polynomial in $1\/\\epsilon$. Our main tool is a new \u201cconditional\u201d version of the regularity lemma for binary matrices, which may be interesting on its own.<\/jats:p>","DOI":"10.1137\/050627915","type":"journal-article","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T18:01:55Z","timestamp":1188410515000},"page":"959-976","source":"Crossref","is-referenced-by-count":36,"title":["Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs"],"prefix":"10.1137","volume":"37","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eldar","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,8,29]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102410973"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.008"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., John Wiley, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R7","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 2nd ed., Springer-Verlag, New York, 2000."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20037"},{"key":"R9","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"E. Fischer and I. Newman,\n                      Testing of matrix properties\n                      , in Proceedings of the 33rd ACM Annual Symposium on Theory of Computing, ACM, New York, 2001, pp. 286\u2013295.","DOI":"10.1145\/380752.380812"},{"key":"R11","unstructured":"E. Fischer and I. Newman,\n                      Testing of matrix-poset properties\n                      , Combinatorica, to appear."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"R16","unstructured":"D. Ron,\n                      Property testing (a tutorial)\n                      , in Handbook of Randomized Computing, Vol. II, S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. D. P. Rolim, eds., Kluwer Academic Publishers, Boston, 2001, pp. 597\u2013649."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"R19","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Problems combinatoires et th\u00e9orie des graphes, Colloq. Internat. CNRS 260, J. C. Bermond, J. C. Fournier, M. Las Vergnas, and D. Sotteau, eds., CNRS, Paris, 1978, pp. 399\u2013401."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"R21","unstructured":"K. Zarankiewicz,\n                      Problem P\n                      101, Colloq. Math., 2 (1951), pp. 116\u2013131."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050627915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:45Z","timestamp":1787336685000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050627915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/050627915"],"URL":"https:\/\/doi.org\/10.1137\/050627915","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}