{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:15Z","timestamp":1759638855824},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319341705"},{"type":"electronic","value":"9783319341712"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-34171-2_29","type":"book-chapter","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T02:34:18Z","timestamp":1464575658000},"page":"409-424","source":"Crossref","is-referenced-by-count":4,"title":["Fourier Sparsity of GF(2) Polynomials"],"prefix":"10.1007","author":[{"given":"Hing Yin","family":"Tsang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengyu","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/978-3-642-32512-0_29","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"A Ada","year":"2012","unstructured":"Ada, A., Fawzi, O., Hatami, H.: Spectral norm of symmetric functions. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol. 7408, pp. 338\u2013349. Springer, Heidelberg (2012)"},{"issue":"3","key":"29_CR2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1109\/12.755000","volume":"48","author":"A Bernasconi","year":"1999","unstructured":"Bernasconi, A., Codenotti, B.: Spectral analysis of boolean functions as a graph eigenvalue problem. IEEE Trans. Comput. 48(3), 345\u2013351 (1999)","journal-title":"IEEE Trans. Comput."},{"key":"29_CR3","unstructured":"Cohen, G., Tal, A.: Two structural results for low degree polynomials and applications. ECCC. TR13-145 (2013)"},{"key":"29_CR4","doi-asserted-by":"crossref","first-page":"589","DOI":"10.2307\/2304500","volume":"54","author":"N Fine","year":"1947","unstructured":"Fine, N.: Binomial coefficients modulo a prime. Am. Math. Mon. 54, 589\u2013592 (1947)","journal-title":"Am. Math. Mon."},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Pitassi, T., Watson, T.: Deterministic communication vs. partition number. In: Proceedings of the 56th Annual Symposium on Foundations of Computer Science, pp. 1077\u20131088 (2015)","DOI":"10.1109\/FOCS.2015.70"},{"issue":"4","key":"29_CR6","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1137\/100785429","volume":"40","author":"P Gopalan","year":"2011","unstructured":"Gopalan, P., O\u2019Donnell, R., Servedio, R., Shpilka, A., Wimme, K.: Testing Fourier dimensionality and sparsity. SIAM J. Comput. 40(4), 1075\u20131100 (2011)","journal-title":"SIAM J. Comput."},{"key":"29_CR7","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/978-3-642-14165-2_41","volume-title":"Automata, Languages and Programming","author":"T Lee","year":"2010","unstructured":"Lee, T., Zhang, S.: Composition theorems in communication complexity. In: Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G., Abramsky, S. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 475\u2013489. Springer, Heidelberg (2010)"},{"key":"29_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/978-3-642-20877-5_39","volume-title":"Theory and Applications of Models of Computation","author":"ML Leung","year":"2011","unstructured":"Leung, M.L., Li, Y., Zhang, S.: Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 403\u2013408. Springer, Heidelberg (2011)"},{"key":"29_CR10","first-page":"10","volume":"20","author":"Y Liu","year":"2013","unstructured":"Liu, Y., Zhang, S.: Quantum and randomized communication complexity of XOR functions in the SMP model. ECCC 20, 10 (2013)","journal-title":"ECCC"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Saks, M.E.: Lattices, M\u00f6bius functions and communication complexity. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 81\u201390 (1988)","DOI":"10.1109\/SFCS.1988.21924"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Lovett, S.: Communication is bounded by root of rank. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 842\u2013846 (2014)","DOI":"10.1145\/2591796.2591799"},{"key":"29_CR13","first-page":"18","volume":"112","author":"S Lovett","year":"2014","unstructured":"Lovett, S.: Recent advances on the log rank conjecture. Bull. EATCS 112, 18\u201336 (2014)","journal-title":"Bull. EATCS"},{"key":"29_CR14","unstructured":"Montanaro, A., Osborne, T.: On the communication complexity of XOR functions (2010). http:\/\/arxiv.org\/abs\/0909.3392v2"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Shpilka, A., Tal, A., Volk, B.L.: On the structure of boolean functions with small spectral norm. In: Proceedings of the 5th Innovations in Theoretical Computer Science (2014)","DOI":"10.1145\/2554797.2554803"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Tsang, H.Y., Wong, C.H., Xie, N., Zhang, S.: Fourier sparsity, spectral norm, and the log-rank conjecture. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 658\u2013667 (2013)","DOI":"10.1109\/FOCS.2013.76"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Yao, A.: Some complexity questions related to distributive computing. In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"},{"issue":"3","key":"29_CR18","first-page":"255","volume":"9","author":"Z Zhang","year":"2009","unstructured":"Zhang, Z., Shi, Y.: Communication complexities of symmetric XOR functions. Quant. Inf. Comput. 9(3), 255\u2013263 (2009)","journal-title":"Quant. Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-34171-2_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T21:14:19Z","timestamp":1567977259000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-34171-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319341705","9783319341712"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-34171-2_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}