{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:53:12Z","timestamp":1787385192720,"version":"build-2736575974"},"reference-count":23,"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":[[2000,1]]},"abstract":"<jats:p>Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P, that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck. We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some nonlinear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems.<\/jats:p>","DOI":"10.1137\/s0097539796311168","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1630-1651","source":"Crossref","is-referenced-by-count":6,"title":["Self-Testing without the Generator Bottleneck"],"prefix":"10.1137","volume":"29","author":[{"given":"Funda","family":"Erg\u00fcn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D.","family":"Sivakumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Ar, M. Blum, B. Codenotti, and P. Gemmell,\n                      Checking approximate computations over the reals\n                      , in Proceedings 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 786\u2013795.","DOI":"10.1145\/167088.167288"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Donald Beaver, Joan Feigenbaum, Hiding instances in multioracle queries (extended abstract), Lecture Notes in Comput. Sci., Vol. 415, Springer, Berlin, 1990, 37\u2013481063302","DOI":"10.1007\/3-540-52282-4_30"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan,\n                      Designing programs that check their work\n                      , in Proceedings 21st Annual ACM Symposium on the Theory of Computing, 1989, pp. 86\u201397.","DOI":"10.1145\/73007.73015"},{"key":"R5","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":"R6","doi-asserted-by":"crossref","unstructured":"Manuel Blum, Hal Wasserman, Program result\u2010checking: a theory of testing meets a test of theory, IEEE Comput. Soc. Press, Los Alamitos, CA, 1994, 382\u20133921489245","DOI":"10.1109\/SFCS.1994.365678"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/12.494097"},{"key":"R8","unstructured":"E. Castillo and M. R. Ruiz\u2010Cobo,\n                      Functional Equations and Modeling in Science and Engineering\n                      , Marcel Dekker, New York, 1992."},{"key":"R9","unstructured":"R. Cleve and M. Luby,\n                      A Note on Self\u2010Testing\/Correcting Methods for Trigonometric Functions\n                      , Technical Report 90\u2010032, ICSI, Berkeley, 1990."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"F. Erg\u00fcn,\n                      Testing multivariate linear functions: Overcoming the generator bottleneck\n                      , in Proceedings 27th Annual ACM Symposium on the Theory of Computing, 1995, pp. 407\u2013416.","DOI":"10.1145\/225058.225167"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Joan Feigenbaum, Locally random reductions in interactive complexity theory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 13, Amer. Math. Soc., Providence, RI, 1993, 73\u20139894k:68058","DOI":"10.1090\/dimacs\/013\/05"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy,\n                      Approximating clique is almost NP\u2010complete\n                      , in Proceedings 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R\u016bsin\u02db\u0161 Freivalds, Fast probabilistic algorithms, Lecture Notes in Comput. Sci., Vol. 74, Springer, Berlin, 1979, 57\u20136982a:68089","DOI":"10.1007\/3-540-09526-8_5"},{"key":"R14","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 23rd Annual ACM Symposium on the Theory of Computing, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Ravikumar, D. Sivakumar, On self\u2010testing without the generator bottleneck, Lecture Notes in Comput. Sci., Vol. 1026, Springer, Berlin, 1995, 248\u201326298b:68115","DOI":"10.1007\/3-540-60692-0_53"},{"key":"R17","unstructured":"Richard Lipton, New directions in testing, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 2, Amer. Math. Soc., Providence, RI, 1991, 191\u201320292c:68127"},{"key":"R18","unstructured":"R. Rubinfeld\n                      private communication\n                      ."},{"key":"R19","unstructured":"Ronitt Rubinfeld, Madhu Sudan, Self\u2010testing polynomial functions efficiently and over rational domains, ACM, New York, 1992, 23\u20133293f:68067"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R21","unstructured":"R. Rubinfeld,\n                      A Mathematical Theory of Self\u2010Checking, Self\u2010Testing, and Self\u2010Correcting Programs\n                      , Ph.D. Thesis, University of California at Berkeley, Berkeley, CA, 1990."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. Rubinfeld,\n                      Robust functional equations with applications to self\u2010testing\/ correcting\n                      , in Proceedings 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 288\u2013299.","DOI":"10.1109\/SFCS.1994.365686"},{"key":"R23","unstructured":"M. Sudan,\n                      On the role of algebra in the efficient verification of proofs\n                      , in Proceedings Workshop on Algebraic Methods in Complexity Theory, M. Agrawal, V. Arvind, and M. Mahajan, eds., 1994, pp. 58\u201368."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796311168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:44Z","timestamp":1787336324000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796311168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539796311168"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796311168","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}