{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:05:01Z","timestamp":1742922301004,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_11","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"123-134","source":"Crossref","is-referenced-by-count":5,"title":["An Algebraic Characterization of Testable Boolean CSPs"],"prefix":"10.1007","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"11_CR1","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(2), 252\u2013271 (1996)","journal-title":"SIAM J. on Comput."},{"issue":"4","key":"11_CR2","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. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. on Comput.\u00a035(1), 1\u201321 (2006)","journal-title":"SIAM J. on Comput."},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Yoshida, Y.: Testing list H-homomorphisms. In: Proc. 27th Annual IEEE Conference on Computational Complexity, pp. 85\u201395 (2012)","DOI":"10.1109\/CCC.2012.9"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"A.A. Bulatov","year":"2000","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, p. 272. Springer, Heidelberg (2000)"},{"issue":"1-2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200(1-2), 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proc. 10th Annual ACM Symposium on the Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"6","key":"11_CR9","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1137\/06064888X","volume":"37","author":"N. Alon","year":"2008","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. on Comput.\u00a037(6), 1703\u20131727 (2008)","journal-title":"SIAM J. on Comput."},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In: Proc. 38th Annual ACM Symposium on Theory of Computing, pp. 251\u2013260 (2006)","DOI":"10.1145\/1132516.1132555"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J.T., Lov\u00e1sz, L., S\u00f3s, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: Proc. 36th Annual ACM Symposium on the Theory of Computing, pp. 261\u2013270 (2006)","DOI":"10.1145\/1132516.1132556"},{"key":"11_CR12","doi-asserted-by":"crossref","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 (2008)","DOI":"10.1145\/1374376.1374434"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Shapira, A.: A unified framework for testing linear-invariant properties. In: Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 478\u2013487 (2010)","DOI":"10.1109\/FOCS.2010.53"},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M. Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM\u00a054(1), 1\u201324 (2007)","journal-title":"J. ACM"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Post, E.: The two-valued iterative systems of mathematical logic. Annals of Mathematics Studies, vol.\u00a05. Princeton Univ. Pr. (1941)","DOI":"10.1515\/9781400882366"},{"issue":"4","key":"11_CR16","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.jcss.2008.11.001","volume":"75","author":"E. Allender","year":"2009","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: Refining Schaefer\u2019s theorem. J. Comp. Sys. Sci.\u00a075(4), 245\u2013254 (2009)","journal-title":"J. Comp. Sys. Sci."},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Inform. and Comput.\u00a0125(1), 1\u201312 (1996)","journal-title":"Inform. and Comput."},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-540-74208-1_28","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Chakraborty","year":"2007","unstructured":"Chakraborty, S., Fischer, E., Lachish, O., Matsliah, A., Newman, I.: Testing st-connectivity. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 380\u2013394. Springer, Heidelberg (2007)"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-642-16367-8_8","volume-title":"Property Testing","author":"I. Newman","year":"2010","unstructured":"Newman, I.: Property testing of massively parametrized problems - A survey. In: Goldreich, O. (ed.) Property Testing. LNCS, vol.\u00a06390, pp. 142\u2013157. Springer, Heidelberg (2010)"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4) (2008)","DOI":"10.1145\/1391289.1391291"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T11:47:45Z","timestamp":1674128865000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}