{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T23:23:42Z","timestamp":1791069822915,"version":"4.1.0"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750] and inspired by Rubinfeld and Sudan [SIAM J. Comput., 25 (1996), pp. 252--271], deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x has the property or is \"far\" from having the property.<\/jats:p>\n                  <jats:p>\n                    The main result here is that, if ${\\cal G}= \\{ g_n:\\{0,1\\}^n \\rightarrow \\{0,1\\} \\}$ is a family of Boolean functions which have oblivious read-once branching programs of width w, then, for every n and $\\epsilon &gt; 0$, there is a randomized algorithm that always accepts every $x \\in \\{0,1\\}^n$ if $g_n(x)=1$ and rejects it with high probability if at least $\\epsilon n$ bits of x should be modified in order for it to be in g\n                    <jats:sub>n<\/jats:sub>\n                    <jats:sup>-1<\/jats:sup>\n                    (1). The algorithm makes $(\\frac{2^{w}}{\\epsilon})^{O(w)}$ queries. In particular, for constant $\\epsilon$ and w, the query complexity is O(1).\n                  <\/jats:p>\n                  <jats:p>This generalizes the results of Alon et al.\\ [Proceedings of the40th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 1999, pp. 645--655] asserting that regular languages are $\\epsilon$-testable for every $\\epsilon &gt; 0$.<\/jats:p>","DOI":"10.1137\/s009753970038211x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1557-1570","source":"Crossref","is-referenced-by-count":36,"title":["Testing Membership in Languages that Have Small Width Branching Programs"],"prefix":"10.1137","volume":"31","author":[{"given":"Ilan","family":"Newman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy,\n                      Efficient testing of large graphs\n                      , in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 656\u2013666.","DOI":"10.1109\/SFFCS.1999.814642"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Krivelevich, I. Newman, and M. Szegedy,\n                      Regular languages are testable with a constant number of queries\n                      , in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 645\u2013655.","DOI":"10.1109\/SFFCS.1999.814641"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"P. Beame, M. Saks, and J. S. Thathachar,\n                      Time\u2010space tradeoffs for branching programs\n                      , in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1998, pp. 254\u2013263.","DOI":"10.1109\/SFCS.1998.743453"},{"key":"R6","unstructured":"Manuel Blum, Michael Luby, Ronitt Rubinfeld, Self\u2010testing\/correcting with applications to numerical problems, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 549\u201359594m:65020"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Ravi Boppana, Michael Sipser, The complexity of finite functions, Elsevier, Amsterdam, 1990, 757\u20138041127180","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Cobham,\n                      The recognition problem for the set of perfect squares\n                      , in Proceedings of the 7th IEEE Symposium on Switching and Automata Theory, Berkeley, CA, 1966, pp. 78\u201387.","DOI":"10.1109\/SWAT.1966.30"},{"key":"R9","unstructured":"E. Fischer and I. Newman,\n                      Functions that have read\u2010twice, constant width, branching programs are not necessarily testable\n                      , to appear in the International Workshop on the Aspects of Complexity and Its Applications, University of Rome La Sapienza, Rome, Italy, 2002."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self\u2010testing\/ correcting for polynomials and for approximate functions\n                      , in Proceedings of the 23rd ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, P. L. Lewis II, and R. E. Stearns,\n                      Hierarchies of memory\u2010limited computations\n                      , in Proceedings of the 6th IEEE Symposium on Switching Circuits and Logic Design, IEEE Computer Society, Los Alamitos, CA, 1965, pp. 179\u2013190.","DOI":"10.1109\/FOCS.1965.11"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"S. Jukna, A. Razborov, P. Savick\u00fd, I. Wegener, On P versus NP\u2229\u221e-NP for decision trees and read\u2010once branching programs, Lecture Notes in Comput. Sci., Vol. 1295, Springer, Berlin, 1997, 319\u201332699e:68053","DOI":"10.1007\/BFb0029975"},{"key":"R14","volume-title":"Computational complexity","author":"Papadimitriou Christos","year":"1994"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Parnas, D. Ron, and R. Rubinfeld,\n                      Testing parenthesis languages\n                      , in Proceedings of APPROX\/RANDOM 2001, Lecture Notes in Comput. Sci. 2129, Springer\u2010Verlag, New York, 2001, pp. 261\u2013272.","DOI":"10.1007\/3-540-44666-4_29"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753970038211X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:25Z","timestamp":1787336545000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753970038211X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1137\/S009753970038211X"],"URL":"https:\/\/doi.org\/10.1137\/s009753970038211x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}