{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T14:23:19Z","timestamp":1776694999061,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642163661","type":"print"},{"value":"9783642163678","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_18","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"260-268","source":"Crossref","is-referenced-by-count":1,"title":["Testing Linear-Invariant Non-linear Properties: A Short Report"],"prefix":"10.1007","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"11","key":"18_CR1","doi-asserted-by":"publisher","first-page":"4032","DOI":"10.1109\/TIT.2005.856958","volume":"51","author":"N. Alon","year":"2005","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing Reed-Muller codes. IEEE Transactions on Information Theory\u00a051(11), 4032\u20134039 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR2","unstructured":"Austin, T., Tao, T.: On the testability and repair of hereditary hypergraph properties. Random Structures and Algorithms (2008) (to appear), http:\/\/arxiv.org\/abs\/0801.2179"},{"key":"18_CR3","unstructured":"Bhattacharyya, A., Chen, V., Sudan, M., Xie, N.: Testing linear-invariant non-linear properties. In: Symposium on Theoretical Aspects of Computer Science, pp. 135\u2013146 (2009)"},{"issue":"1","key":"18_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01(1), 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Shapira, A.: A unified framework for testing linear-invariant properties. To appear in FOCS (2010)","DOI":"10.1109\/FOCS.2010.53"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comp. Sys. Sci.\u00a047, 549\u2013595 (1993); Earlier version in STOC 1990","journal-title":"J. Comp. Sys. Sci."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Xie, N.: Lower bounds for testing triangle-freeness in boolean functions. In: Proc. 21st ACM-SIAM Symposium on Discrete Algorithms, pp. 87\u201398 (2010)","DOI":"10.1137\/1.9781611973075.9"},{"key":"18_CR8","unstructured":"Fox, J.: A new proof of the graph removal lemma. Technical report (June 2010), http:\/\/arxiv.org\/abs\/1006.1300"},{"issue":"2","key":"18_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/rsa.10017","volume":"20","author":"P. Frankl","year":"2002","unstructured":"Frankl, P., R\u00f6dl, V.: Extremal problems on set systems. Random Structures and Algorithms\u00a020(2), 131\u2013164 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045, 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"issue":"3","key":"18_CR11","doi-asserted-by":"publisher","first-page":"897","DOI":"10.4007\/annals.2007.166.897","volume":"166","author":"W.T. Gowers","year":"2007","unstructured":"Gowers, W.T.: Hypergraph regularity and the multidimensional Szemer\u00e9di theorem. Annals of Mathematics\u00a0166(3), 897\u2013946 (2007)","journal-title":"Annals of Mathematics"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: On proximity oblivious testing. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 141\u2013150 (2009)","DOI":"10.1145\/1536414.1536436"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/s00039-005-0509-8","volume":"15","author":"B. Green","year":"2005","unstructured":"Green, B.: A Szemer\u00e9di-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal.\u00a015(2), 340\u2013376 (2005)","journal-title":"Geom. Funct. Anal."},{"key":"18_CR14","unstructured":"Green, B., Tao, T.: Linear equations in primes. Annals of Mathematics (2006) (to appear)"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 423\u2013432 (2004)","DOI":"10.1109\/FOCS.2004.64"},{"issue":"3","key":"18_CR16","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1137\/S0097539704445615","volume":"36","author":"T. Kaufman","year":"2006","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM J. on Comput.\u00a036(3), 779\u2013802 (2006)","journal-title":"SIAM J. on Comput."},{"key":"18_CR17","first-page":"403","volume-title":"Proc. 40th Annual ACM Symposium on the Theory of Computing","author":"T. Kaufman","year":"2008","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Proc. 40th Annual ACM Symposium on the Theory of Computing, pp. 403\u2013412. ACM, New York (2008)"},{"key":"18_CR18","unstructured":"Kr\u00e1l\u2019, D., Serra, O., Vena, L.: A removal lemma for systems of linear equations over finite fields (2008)"},{"issue":"4","key":"18_CR19","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/j.jcta.2008.12.003","volume":"116","author":"D. Kr\u00e1l","year":"2009","unstructured":"Kr\u00e1l, D., Serra, O., Vena, L.: A combinatorial proof of the removal lemma for groups. Journal of Combinatorial Theory\u00a0116(4), 971\u2013978 (2009)","journal-title":"Journal of Combinatorial Theory"},{"issue":"2","key":"18_CR20","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1002\/rsa.20117","volume":"28","author":"B. Nagle","year":"2006","unstructured":"Nagle, B., R\u00f6dl, V., Schacht, M.: The counting lemma for regular k-uniform hypergraphs. Random Structures and Algorithms\u00a028(2), 113\u2013179 (2006)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. on Comput.\u00a025, 252\u2013271 (1996)","journal-title":"SIAM J. on Comput."},{"issue":"1","key":"18_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20017","volume":"25","author":"V. R\u00f6dl","year":"2004","unstructured":"R\u00f6dl, V., Skokan, J.: Regularity lemma for k-uniform hypergraphs. Random Structures and Algorithms\u00a025(1), 1\u201342 (2004)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Shapira, A.: Green\u2019s conjecture and testing linear-invariant properties. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 159\u2013166 (2009)","DOI":"10.1145\/1536414.1536438"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T13:18:01Z","timestamp":1740575881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}