{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:03Z","timestamp":1725745263088},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_39","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"559-574","source":"Crossref","is-referenced-by-count":3,"title":["Tight Lower Bounds for Testing Linear Isomorphism"],"prefix":"10.1007","author":[{"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karl","family":"Wimmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","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. Journal of Computer and System Sciences\u00a047, 549\u2013595 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"39_CR2","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 Journal on Computing\u00a025, 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR3","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":"1","key":"39_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: It\u2019s all about regularity. SIAM J. Comput.\u00a039(1), 143\u2013167 (2009)","journal-title":"SIAM J. Comput."},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J.T., Lov\u00e1sz, L., S\u00f3s, V., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: STOC, pp. 261\u2013270 (2006)","DOI":"10.1145\/1132516.1132556"},{"key":"39_CR6","unstructured":"Bhattacharyya, A., Fischer, E., Hatami, H., Lovett, P.H.S.: Every locally characterized affine-invariant property is testable. In: STOC (to appear, 2013)"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: The role of invariance. In: STOC, pp. 403\u2013412 (2008)","DOI":"10.1145\/1374376.1374434"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: 2-transitivity is insufficient for local testability. Computational Complexity\u00a022(1) (2013)","DOI":"10.1007\/s00037-012-0055-3"},{"issue":"4","key":"39_CR9","doi-asserted-by":"publisher","first-page":"1618","DOI":"10.1137\/100818364","volume":"26","author":"E. Grigorescu","year":"2012","unstructured":"Grigorescu, E., Kaufman, T., Sudan, M.: Succinct representation of codes with applications to testing. SIAM J. Discrete Math.\u00a026(4), 1618\u20131634 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-642-22935-0_35","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Ben-Sasson","year":"2011","unstructured":"Ben-Sasson, E., Sudan, M.: Limits on the rate of locally testable affine-invariant codes. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX \/RANDOM 2011. LNCS, vol.\u00a06845, pp. 412\u2013423. Springer, Heidelberg (2011)"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Maatouk, G., Shpilka, A., Sudan, M.: Symmetric LDPC codes are not necessarily locally testable. In: CCC, pp. 55\u201365 (2011)","DOI":"10.1109\/CCC.2011.14"},{"key":"39_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-642-22935-0_34","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Ben-Sasson","year":"2011","unstructured":"Ben-Sasson, E., Grigorescu, E., Maatouk, G., Shpilka, A., Sudan, M.: On sums of locally testable affine invariant properties. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2011. LNCS, vol.\u00a06845, pp. 400\u2013411. Springer, Heidelberg (2011)"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Lovett, S.: New extension of the weil bound for character sums with applications to coding. In: FOCS, pp. 788\u2013796 (2011)","DOI":"10.1109\/FOCS.2011.41"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Ron-Zewi, N., Sudan, M.: Sparse affine-invariant linear codes are locally testable. In: FOCS, pp. 561\u2013570 (2012)","DOI":"10.1109\/FOCS.2012.38"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Guo, A., Kopparty, S., Sudan, M.: New affine-invariant codes from lifting. In: ITCS, pp. 529\u2013540 (2013)","DOI":"10.1145\/2422436.2422494"},{"issue":"2","key":"39_CR16","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."},{"issue":"4","key":"39_CR17","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/j.jcta.2008.12.003","volume":"116","author":"D. Kr\u00e1l\u2019","year":"2009","unstructured":"Kr\u00e1l\u2019, D., Serra, O., Vena, L.: A combinatorial proof of the removal lemma for groups. Journal of Combinatorial Theory (A)\u00a0116(4), 971\u2013978 (2009)","journal-title":"Journal of Combinatorial Theory (A)"},{"key":"39_CR18","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"},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Shapira, A.: A unified framework for testing linear-invariant properties. In: FOCS, pp. 478\u2013487 (2010)","DOI":"10.1109\/FOCS.2010.53"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Blais, E., O\u2019Donnell, R.: Lower bounds for testing function isomorphism. In: Proc. 25th Annual IEEE Conference on Computational Complexity, pp. 235\u2013246 (2010)","DOI":"10.1109\/CCC.2010.30"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Alon, N., Blais, E.: Testing boolean function isomorphism. In: Proc. 14th International Workshop on Randomization and Computation, pp. 394\u2013405 (2010)","DOI":"10.1007\/978-3-642-15369-3_30"},{"key":"39_CR22","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Garc\u00eda-Soriano, D., Matsliah, A.: Nearly tight bounds for testing function isomorphism. In: SODA, pp. 1683\u20131702 (2011)","DOI":"10.1137\/1.9781611973082.130"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Fischer, E., Garc\u00eda-Soriano, D., Matsliah, A.: Junto-symmetric functions, hypergraph isomorphism and crunching. In: CCC, pp. 148\u2013158 (2012)","DOI":"10.1109\/CCC.2012.28"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Blais, E., Weinstein, A., Yoshida, Y.: Partially symmetric functions are efficiently isomorphism-testable. In: FOCS, pp. 551\u2013560 (2012)","DOI":"10.1109\/FOCS.2012.53"},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"Blais, E., Kane, D.: Tight bounds for testing k-linearity. In: Proc. 16th International Workshop on Randomization and Computation, pp. 435\u2013446 (2012)","DOI":"10.1007\/978-3-642-32512-0_37"},{"key":"39_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0097-3165(73)90031-9","volume":"15","author":"R. McFarland","year":"1973","unstructured":"McFarland, R.: A family of difference sets in non-cyclic groups. Journal of Combinatorial Theory (A)\u00a015, 1\u201310 (1973)","journal-title":"Journal of Combinatorial Theory (A)"},{"key":"39_CR27","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0097-3165(76)90024-8","volume":"20","author":"O. Rothaus","year":"1976","unstructured":"Rothaus, O.: On \u201cbent\u201d functions. Journal of Combinatorial Theory (A)\u00a020, 300\u2013305 (1976)","journal-title":"Journal of Combinatorial Theory (A)"},{"issue":"2","key":"39_CR28","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1008283912025","volume":"14","author":"C. Carlet","year":"1998","unstructured":"Carlet, C., Guillot, P.: An alternate characterization of the bentness of binary functions, with uniqueness. Des. Codes Cryptography\u00a014(2), 133\u2013140 (1998)","journal-title":"Des. Codes Cryptography"},{"issue":"1","key":"39_CR29","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.jda.2006.08.004","volume":"6","author":"C. Charnes","year":"2008","unstructured":"Charnes, C., Dempwolff, U., Pieprzyk, J.: The eight variable homogeneous degree three bent functions. J. Discrete Algorithms\u00a06(1), 66\u201372 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"39_CR30","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s10623-011-9511-3","volume":"62","author":"U. Dempwolff","year":"2012","unstructured":"Dempwolff, U.: Geometric and design-theoretic aspects of semibent functions ii. Des. Codes Cryptography\u00a062(2), 241\u2013252 (2012)","journal-title":"Des. Codes Cryptography"},{"issue":"1-3","key":"39_CR31","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10623-010-9466-9","volume":"59","author":"L. Budaghyan","year":"2011","unstructured":"Budaghyan, L., Carlet, C.: Ccz-equivalence of bent vectorial functions and related constructions. Des. Codes Cryptography\u00a059(1-3), 69\u201387 (2011)","journal-title":"Des. Codes Cryptography"},{"issue":"1-3","key":"39_CR32","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s10623-010-9468-7","volume":"59","author":"C. Carlet","year":"2011","unstructured":"Carlet, C.: Relating three nonlinearity parameters of vectorial functions and building apn functions from bent functions. Des. Codes Cryptography\u00a059(1-3), 89\u2013109 (2011)","journal-title":"Des. Codes Cryptography"},{"key":"39_CR33","unstructured":"Neumann, T.: Bent functions. Master\u2019s thesis, University of Kaiserslautern (2006)"},{"key":"39_CR34","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Xie, N.: Lower bounds on 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":"39_CR35","unstructured":"Tokareva, N.: On the number of bent functions: lower bounds and hypotheses. IACR Cryptology ePrint Archive,\u00a083 (2011)"},{"issue":"1","key":"39_CR36","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2003","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic Boolean formulae. SIAM Journal on Discrete Mathematics\u00a016(1), 20\u201346 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"39_CR37","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"E. Fischer","year":"2004","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. Journal of Computer and System Sciences\u00a068(4), 753\u2013787 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"39_CR38","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/100785429","volume":"40","author":"P. Gopalan","year":"2011","unstructured":"Gopalan, P., O\u2019Donnell, R., Servedio, R., Shpilka, A., Wimmer, K.: Testing Fourier dimensionality and sparsity. SIAM Journal on Computing\u00a040(4), 1075\u20131100 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR39","unstructured":"Wimmer, K., Yoshida, Y.: Testing linear-invariant function isomorphism. In: ICALP (to appear, 2013)"},{"issue":"2","key":"39_CR40","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00037-012-0040-x","volume":"21","author":"E. Blais","year":"2012","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. Computational Complexity\u00a021(2), 311\u2013358 (2012)","journal-title":"Computational Complexity"},{"key":"39_CR41","unstructured":"Sun, X., Wang, C.: Randomized communication complexity for linear algebra problems over finite fields. In: Proc. 29th Annual Symposium on Theoretical Aspects of Computer Science, pp. 477\u2013488 (2012)"},{"key":"39_CR42","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:56:41Z","timestamp":1558029401000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}