乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:40:14Z","timestamp":1737078014099,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":61,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540433286"},{"type":"electronic","value":"9783540458784"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45878-6_2","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T01:21:43Z","timestamp":1181179303000},"page":"30-83","source":"Crossref","is-referenced-by-count":7,"title":["Exact and Approximate Testing\/Correcting of Algebraic Functions: A Survey"],"prefix":"10.1007","author":[{"given":"Marcos","family":"Kiwi","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Magniez","sequence":"additional","affiliation":[]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"S. Ar, M. Blum, B. Codenotti, and P. Gemmell. Checking approximate computations over the reals. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 786\u2013795, San Diego, California, May 1993. ACM.","DOI":"10.1145\/167088.167288"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, S. Dar, M. Parnas, and D. Ron. Testing clustering. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000. (To appear).","DOI":"10.1109\/SFCS.2000.892111"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 656\u2013666, New York City, New York, October 1999. IEEE.","DOI":"10.1109\/SFFCS.1999.814642"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Krivelevich, I. Newman, and M. Szegedy. Regular languages are testable with a constant number of queries. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 645\u2013655, New York City, New York, October 1999. IEEE.","DOI":"10.1109\/SFFCS.1999.814641"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 14\u201323, Pittsburgh, Pennsylvania, October 1992. IEEE. Final version in [ALM+98].","DOI":"10.1109\/SFCS.1992.267823"},{"issue":"3","key":"2_CR6","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. J. of the Association for Computing Machinery, 45(3):505\u2013555, 1998.","journal-title":"J. of the Association for Computing Machinery"},{"key":"2_CR7","unstructured":"N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., first edition, 1992."},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 2\u201313, Pittsburgh, Pennsylvania, October 1992. IEEE.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"S. Arora and M. Sudan. Improved low-degree testing and its applications. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 485\u2013495, El Paso, Texas, May 1997. ACM.","DOI":"10.1145\/258533.258642"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"M. Bellare, D. Coppersmith, J. Hoastad, M. Kiwi, and M. Sudan. Linearity testing in characteristic two. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 432\u2013441, Milwaukee, Wisconsin, October 1995. IEEE.","DOI":"10.1109\/SFCS.1995.492574"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 16\u201325, St. Louis, Missouri, October 1990. IEEE. Final version in [BFL91].","DOI":"10.1109\/FSCS.1990.89520"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3\u201340, 1991.","journal-title":"Computational Complexity"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 21\u201331, New Orleans, Louisiana, May 1991. ACM.","DOI":"10.1145\/103418.103428"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 294\u2013304, San Diego, California, May 1993. ACM.","DOI":"10.1145\/167088.167174"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan. Designing programs that check their work. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 86\u201397, Seattle, Washington, May 1989. ACM. Final version in [BK95].","DOI":"10.1145\/73007.73015"},{"issue":"1","key":"2_CR16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"M. Blum and S. Kannan. Designing programs that check their work. J. of the Association for Computing Machinery, 42(1):269\u2013291, 1995.","journal-title":"J. of the Association for Computing Machinery"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"M. Blum, M. Luby, and R. Rubinfeld. Self-testing\/correcting with applications to numerical problems. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 73\u201383, Baltimore, Maryland, May 1990. ACM. Final version in [BLR93].","DOI":"10.1145\/100216.100225"},{"issue":"3","key":"2_CR18","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"M. Blum, M. Luby, and R. Rubinfeld. Self-testing\/correcting with applications to numerical problems. J. of Computer and System Sciences, 47(3):549\u2013595, 1993.","journal-title":"J. of Computer and System Sciences"},{"key":"2_CR19","unstructured":"M. Blum. Designing programs to check their work. Technical Report TR-88-009, International Computer Science Institure, 1988."},{"key":"2_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1007\/3-540-45022-X_68","volume-title":"Proceedings of the 27th International Colloquium on Automata, Languages and Programming","author":"M. Bender","year":"2000","unstructured":"M. Bender and D. Ron. Testing acyclicity of directed graphs in sublinear time. In Proceedings of the 27th International Colloquium on Automata, Languages and Programming, volume 1853 of LNCS, pages 809\u2013820. Springer-Verlag, 2000."},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan. Improved non-approximability results. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 184\u2013193, Montr\u00e9al, Qu\u00e9bec, Canada, May 1994. ACM.","DOI":"10.1145\/195058.195129"},{"issue":"5","key":"2_CR22","first-page":"1411","volume":"26","author":"M. Blum","year":"1997","unstructured":"M. Blum and H. Wasserman. Reflections on the Pentium division bug. IEEE Trans. Comp., 26(5):1411\u20131473, April 1997.","journal-title":"IEEE Trans. Comp."},{"key":"2_CR23","unstructured":"D. Coppersmith. Manuscript. Result described in [BLR90], December 1989."},{"key":"2_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-48413-4_10","volume-title":"Proceedings of RANDOM\u201999","author":"Y. Dodis","year":"1999","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Rsakhodnikova, D. Ron, and A. Samorodnitsky. Improved testing algorithms for monotonicity. In Proceedings of RANDOM\u201999, volume 1671 of LNCS, pages 97\u2013108. Springer-Verlag, 1999."},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"W. van Dam, F. Magniez, M. Mosca, and M. Santha. Self-testing of universal and fault-tolerant sets of quantum gates. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 688\u2013696, Portland, Oregon, May 2000. ACM.","DOI":"10.1145\/335305.335402"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"F. Erg\u00fcn, S. Ravi Kumar, and R. Rubinfeld. Approximate checking of polynomials and functional equations. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 592\u2013601, Burlington, Vermont, October 1996. IEEE.","DOI":"10.1109\/SFCS.1996.548518"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"F. Erg\u00fcn. Testing multivariate linear functions: Overcoming the generator bottleneck. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 407\u2013416, Las Vegas, Nevada, May 1995. ACM.","DOI":"10.1145\/225058.225167"},{"issue":"5","key":"2_CR28","doi-asserted-by":"publisher","first-page":"1630","DOI":"10.1137\/S0097539796311168","volume":"29","author":"F. Erg\u00fcn","year":"2000","unstructured":"F. Erg\u00fcn, S. Sivakumar, and S. Ravi Kumar. Self-testing without the generator bottleneck. SIAM J. on Computing, 29(5):1630\u20131651, 2000.","journal-title":"SIAM J. on Computing"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 2\u201312, San Juan, Puerto Rico, October 1991. IEEE.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF01831117","volume":"50","author":"G. L. Forti","year":"1995","unstructured":"G. L. Forti. Hyers-Ulam stability of functional equations in several variables. Aequationes Mathematicae, 50:143\u2013190, 1995.","journal-title":"Aequationes Mathematicae"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, E. Lehman, and D. Ron. Testing monotonicity. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 426\u2013435, Palo Alto, California, November 1998. IEEE.","DOI":"10.1109\/SFCS.1998.743493"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 339\u2013348, Burlington, Vermont, October 1996. IEEE.","DOI":"10.1109\/SFCS.1996.548493"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-testing\/correcting for polynomials and for approximate functions. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 32\u201342, New Orleans, Louisiana, May 1991. ACM.","DOI":"10.1145\/103418.103429"},{"key":"2_CR34","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1090\/dimacs\/043\/04","volume":"43","author":"O. Goldreich","year":"1998","unstructured":"O. Goldreich. Combinatorial property testing \u2014 A survey, volume 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 45\u201360. ACM\/AMS, 1998.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"2_CR35","unstructured":"O. Goldreich. Talk given at the DIMACS Workshop on Sublinear Algorithms, September 2000."},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"O. Goldreich and D. Ron. Property testing in bounded degree graphs. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 406\u2013415, El Paso, Texas, May 1997. ACM.","DOI":"10.1145\/258533.258627"},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"O. Goldreich and D. Ron. A sublinear bipartiteness tester for bounded degree graphs. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 289\u2013298, Dallas, Texas, May 1998. ACM.","DOI":"10.1145\/276698.276767"},{"key":"2_CR38","unstructured":"O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. Technical Report ECCC TR00-020, Electronic Colloquium on Computational Complexity, 2000. (Available at http:\/\/www.eccc.uni-trier.de\/eccc\/ )."},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Testing of the long code and hardness of clique. In Proceedings of the 37nd Annual IEEE Symposium on Foundations of Computer Science, pages 11\u201319, Burlington, Vermont, October 1996. IEEE.","DOI":"10.1145\/237814.237820"},{"key":"2_CR40","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Getting optimal in-approximability results. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 1\u201310, El Paso, Texas, May 1997. ACM.","DOI":"10.1145\/258533.258536"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01830975","volume":"44","author":"D. H. Hyers","year":"1992","unstructured":"D. H. Hyers and T. M. Rassias. Approximate homomorphisms. Aequationes Mathematicae, 44:125\u2013153, 1992.","journal-title":"Aequationes Mathematicae"},{"key":"2_CR42","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1073\/pnas.27.4.222","volume":"27","author":"D. H. Hyers","year":"1941","unstructured":"D. H. Hyers. On the stability of the linear functional equation. Proceedings of the National Academy of Science, U.S.A., 27:222\u2013224, 1941.","journal-title":"Proceedings of the National Academy of Science"},{"key":"2_CR43","unstructured":"M. Kiwi. Probabilistically Checkable Proofs and the Testing of Hadamard-like Codes. PhD thesis, Massachusetts Institute of Technology, February 1996."},{"key":"2_CR44","doi-asserted-by":"crossref","unstructured":"M. Kiwi, F. Magniez, and M. Santha. Approximate testing with relative error. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 51\u201360, Atlanta, Georgia, May 1999. ACM.","DOI":"10.1145\/301250.301269"},{"key":"2_CR45","unstructured":"M. Kiwi and A. Russell. Linearity testing over prime fields. Unpublished manuscript, 1997."},{"key":"2_CR46","first-page":"191","volume":"2","author":"R. J. Lipton","year":"1991","unstructured":"R. J. Lipton. New directions in testing, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 191\u2013202. ACM\/AMS, 1991.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"2_CR47","unstructured":"F. Magniez. Auto-test pour les calculs approch\u00e9 et quantique. PhD thesis, Universit\u00e9 Paris-Sud, France, 2000."},{"key":"2_CR48","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/3-540-46541-3_25","volume-title":"Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science","author":"F. Magniez","year":"2000","unstructured":"F. Magniez. Multi-linearity self-testing with relative error. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, volume 1770 of LNCS, pages 302\u2013313. Springer-Verlag, 2000."},{"key":"2_CR49","unstructured":"M. Mishra, D. Oblinger, and L. Pirtt. Way-sublinear time approximate (PAC) clustering. Unpublished, 2000."},{"key":"2_CR50","doi-asserted-by":"crossref","unstructured":"I. Newman. Testing of functions that have small width branching programs. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000. (To appear).","DOI":"10.1109\/SFCS.2000.892112"},{"key":"2_CR51","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-540-48413-4_9","volume-title":"Proceedings of RANDOM\u201999","author":"M. Parnas","year":"1999","unstructured":"M. Parnas and D. Ron. Testing the diameter of graphs. In Proceedings of RANDOM\u201999, volume 1671 of LNCS, pages 85\u201396. Springer-Verlag, 1999."},{"key":"2_CR52","doi-asserted-by":"crossref","unstructured":"A. Polishchuk and D. Spielman. Nearly-linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 194\u2013203, Montr\u00e9al, Qu\u00e9bec, Canada, May 1994. ACM.","DOI":"10.1145\/195058.195132"},{"key":"2_CR53","doi-asserted-by":"crossref","unstructured":"D. Ron. Property testing (A tutorial), 2000. (Available at http:\/\/www.eng.tau.ac.il\/?danar\/papers.html ). To appear in Handbook on Randomization.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"2_CR54","unstructured":"R. Rubinfeld. A mathematical theory of self-checking, self-testing and self-correcting programs. PhD thesis, University of California, Berkeley, 1990."},{"key":"2_CR55","doi-asserted-by":"crossref","unstructured":"R. Rubinfeld. On the robustness of functional equations. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 288\u2013299, Santa Fe, New Mexico, November 1994. IEEE. Final version in [Rub99].","DOI":"10.1109\/SFCS.1994.365686"},{"issue":"6","key":"2_CR56","doi-asserted-by":"publisher","first-page":"1972","DOI":"10.1137\/S0097539796298625","volume":"28","author":"R. Rubinfeld","year":"1999","unstructured":"R. Rubinfeld. On the robustness of functional equations. SIAM J. on Computing, 28(6):1972\u20131997, 1999.","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"2_CR57","doi-asserted-by":"publisher","first-page":"989","DOI":"10.2307\/2159617","volume":"114","author":"T. M. Rassias","year":"1992","unstructured":"T. M. Rassias and P. \u0160emrl. On the behaviour of mappings which do not satisfy Hyers-Ulam stability. Proceedings of the American Mathematical Society, 114(4):989\u2013993, April 1992.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2_CR58","unstructured":"R. Rubinfeld and M. Sudan. Testing polynomial functions efficiently and over rational domains. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 23\u201332, Orlando, Florida, January 1992. ACM\/SIAM. Final version in [RS96]."},{"issue":"2","key":"2_CR59","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal of Computing, 25(2):252\u2013271, April 1996.","journal-title":"SIAM Journal of Computing"},{"key":"2_CR60","first-page":"377","volume":"117","author":"F. Skopf","year":"1983","unstructured":"F. Skopf. Sull\u2019approssimazione delle applicazioni localmente \u03b2-additive.Atti della Accademia delle Sciencze di Torino, 117:377\u2013389, 1983. (In Italian.).","journal-title":"Atti della Accademia delle Sciencze di Torino"},{"key":"2_CR61","doi-asserted-by":"crossref","unstructured":"L. Trevisan. Recycling queries in PCPs and in linearity tests. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 299\u2013308, Dallas, Texas, May 1998. ACM.","DOI":"10.1145\/276698.276769"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45878-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:15:32Z","timestamp":1737076532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45878-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433286","9783540458784"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/3-540-45878-6_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}