{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:41:30Z","timestamp":1743100890829,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030794156"},{"type":"electronic","value":"9783030794163"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_28","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"460-483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Generalization of a Theorem of Rothschild and van Lint"],"prefix":"10.1007","author":[{"given":"Ning","family":"Xie","sequence":"first","affiliation":[]},{"given":"Shuai","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Yekun","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"issue":"2","key":"28_CR1","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/140985251","volume":"47","author":"D Aggarwal","year":"2018","unstructured":"Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. SIAM J. Comput. 47(2), 524\u2013546 (2018). Earlier version in STOC\u201914","journal-title":"SIAM J. Comput."},{"issue":"4","key":"28_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/2629598","volume":"61","author":"E Ben-Sasson","year":"2014","unstructured":"Ben-Sasson, E., Lovett, S., Ron-Zewi, N.: An additive combinatorics approach relating rank to communication complexity. J. ACM 61(4), 22 (2014)","journal-title":"J. ACM"},{"issue":"6","key":"28_CR3","doi-asserted-by":"publisher","first-page":"1670","DOI":"10.1137\/12089003X","volume":"44","author":"E Ben-Sasson","year":"2015","unstructured":"Ben-Sasson, E., Ron-Zewi, N.: From affine to two-source extractors via approximate duality. SIAM J. Comput. 44(6), 1670\u20131697 (2015). Earlier version in STOC\u201911","journal-title":"SIAM J. Comput."},{"issue":"3","key":"28_CR4","doi-asserted-by":"publisher","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":"28_CR5","doi-asserted-by":"crossref","unstructured":"Bhowmick, A., Dvir, Z., Lovett, S.: New bounds for matching vector families. In: Proceedings of 45th Annual ACM Symposium on the Theory of Computing, pp. 823\u2013832 (2013)","DOI":"10.1145\/2488608.2488713"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, A., Mande, N., Sherif, S.: The Log-approximate-rank conjecture is false. In: Proceedings of 51st Annual ACM Symposium on the Theory of Computing (2019, to appear)","DOI":"10.1145\/3313276.3316353"},{"key":"28_CR7","unstructured":"Chistopolskaya, A., Podolskii, V.: Parity decision tree complexity is greater than granularity, October 2018. http:\/\/arxiv.org\/abs\/1810.08668"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Chow, C.: On the characterization of threshold functions. In: Proceedings of 2nd Annual IEEE Symposium on Foundations of Computer Science, pp. 34\u201338. IEEE (1961)","DOI":"10.1109\/FOCS.1961.24"},{"issue":"2","key":"28_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2590772","volume":"61","author":"A De","year":"2014","unstructured":"De, A., Diakonikolas, I., Feldman, V., Servedio, R.: Nearly optimal solutions for the Chow parameters problem and low-weight approximation of halfspaces. J. ACM 61(2), 1\u201336 (2014). Earlier version in STOC\u201912","journal-title":"J. ACM"},{"issue":"6","key":"28_CR10","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1017\/S0963548312000351","volume":"21","author":"C Even-Zohar","year":"2012","unstructured":"Even-Zohar, C.: On sums of generating sets in $$\\mathbb{Z}_2^n$$. Comb. Probab. Comput. 21(6), 916\u2013941 (2012)","journal-title":"Comb. Probab. Comput."},{"key":"28_CR11","unstructured":"Freiman, G.: Foundations of a structural theory of set addition. American Mathematical Society, Providence, RI (1973). Translated from the Russian. Translations of Mathematical Monographs, Vol 37"},{"issue":"1","key":"28_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E Friedgut","year":"1998","unstructured":"Friedgut, E.: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18(1), 27\u201335 (1998)","journal-title":"Combinatorica"},{"issue":"3","key":"28_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/S0196-8858(02)00024-6","volume":"29","author":"E Friedgut","year":"2002","unstructured":"Friedgut, E., Kalai, G., Naor, A.: Boolean functions whose Fourier transform is concentrated on the first two levels. Adv. Appl. Math. 29(3), 427\u2013437 (2002)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"28_CR14","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 J. Comput. 40(4), 1075\u20131100 (2011). Earlier version in ICALP\u201909","journal-title":"SIAM J. Comput."},{"issue":"1","key":"28_CR15","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1112\/S0024609305018102","volume":"38","author":"B Green","year":"2006","unstructured":"Green, B., Ruzsa, I.: Sets with small sumset and rectification. Bull. Lond. Math. Soc. 38(1), 43\u201352 (2006)","journal-title":"Bull. Lond. Math. Soc."},{"issue":"3","key":"28_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1017\/S0963548309009821","volume":"18","author":"B Green","year":"2009","unstructured":"Green, B., Tao, T.: Freiman\u2019s theorem in finite fields via extremal set theory. Comb. Probab. Comput. 18(3), 335\u2013355 (2009)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"28_CR17","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1137\/17M1136869","volume":"47","author":"H Hatami","year":"2018","unstructured":"Hatami, H., Hosseini, K., Lovett, S.: Structure of protocols for XOR functions. SIAM J. Comput. 47(1), 208\u2013217 (2018)","journal-title":"SIAM J. Comput."},{"issue":"3\u20134","key":"28_CR18","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1134\/S0001434608090137","volume":"84","author":"S Konyagin","year":"2008","unstructured":"Konyagin, S.: On the Freiman theorem in finite fields. Math. Notes 84(3\u20134), 435\u2013438 (2008)","journal-title":"Math. Notes"},{"issue":"10","key":"28_CR19","doi-asserted-by":"publisher","first-page":"2965","DOI":"10.1090\/S0002-9939-01-06035-X","volume":"129","author":"I \u0141aba","year":"2001","unstructured":"\u0141aba, I.: Fuglede\u2019s conjecture for a union of two intervals. Proc. Am. Math. Soc. 129(10), 2965\u20132972 (2001)","journal-title":"Proc. Am. Math. Soc."},{"key":"28_CR20","unstructured":"Lin, C., Zhang, S.: Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers. In: Proceedings of 44th Annual International Conference on Automata, Languages, and Programming, vol. 80, pp. 51:1\u201351:13 (2017)"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Saks, M.: Lattices, M\u00f6bius functions and communication complexity. In: Proceedings of 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 330\u2013337 (1988)","DOI":"10.1109\/SFCS.1988.21924"},{"key":"28_CR22","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":"28_CR23","doi-asserted-by":"crossref","unstructured":"Lovett, S.: Additive combinatorics and its applications in theoretical computer science. Theory Comput. 1\u201355 (2017)","DOI":"10.4086\/toc.gs.2017.008"},{"key":"28_CR24","volume-title":"The Theory of Error-Correction Codes","author":"FJ MacWilliams","year":"1977","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correction Codes. North Holland, Amsterdam (1977)"},{"key":"28_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"28_CR26","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/090756466","volume":"40","author":"R O\u2019Donnell","year":"2011","unstructured":"O\u2019Donnell, R., Servedio, R.: The Chow parameters problem. SIAM J. Comput. 40(1), 165\u2013199 (2011). Earlier version in STOC\u201908","journal-title":"SIAM J. Comput."},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wright, J., Zhao, Y., Sun, X., Tan, L.Y.: A composition theorem for parity kill number. In: Proceedings of 29th Annual IEEE Conference on Computational Complexity, pp. 144\u2013154 (2014)","DOI":"10.1109\/CCC.2014.22"},{"issue":"1","key":"28_CR28","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0097-3165(74)90075-2","volume":"16","author":"BL Rothschild","year":"1974","unstructured":"Rothschild, B.L., van Lint, J.: Characterizing finite subspaces. J. Comb. Theory Ser. A 16(1), 97\u2013110 (1974)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"199","key":"28_CR29","first-page":"323","volume":"258","author":"I Ruzsa","year":"1999","unstructured":"Ruzsa, I.: An analog of Freiman\u2019s theorem in groups. Ast\u00e9risque 258(199), 323\u2013326 (1999)","journal-title":"Ast\u00e9risque"},{"key":"28_CR30","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A.: Low-degree tests at large distances. In: Proceedings of 39th Annual ACM Symposium on the Theory of Computing, pp. 506\u2013515 (2007)","DOI":"10.1145\/1250790.1250864"},{"issue":"2","key":"28_CR31","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1017\/S0963548307008644","volume":"17","author":"T Sanders","year":"2008","unstructured":"Sanders, T.: A note on Fre\u012dman\u2019s theorem in vector spaces. Comb. Probab. Comput. 17(2), 297\u2013305 (2008)","journal-title":"Comb. Probab. Comput."},{"key":"28_CR32","doi-asserted-by":"crossref","unstructured":"Shpilka, A., Tal, A., lee Volk, B.: On the structure of boolean functions with small spectral norm. Comput. Complex. 26(1), 229\u2013273 (2017)","DOI":"10.1007\/s00037-015-0110-y"},{"key":"28_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755149","volume-title":"Additive Combinatorics","author":"T Tao","year":"2006","unstructured":"Tao, T., Vu, V.: Additive Combinatorics. Cambridge University Press, Cambridge (2006)"},{"key":"28_CR34","doi-asserted-by":"crossref","unstructured":"Tsang, H., Wong, C., Xie, N., Zhang, S.: Fourier sparsity, spectral norm, and the Log-rank conjecture. In: Proceedings of 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 658\u2013667 (2013)","DOI":"10.1109\/FOCS.2013.76"},{"key":"28_CR35","doi-asserted-by":"crossref","unstructured":"Tsang, H., Xie, N., Zhang, S.: Fourier sparsity of GF($$2$$) polynomials. In: Proceedings of the International Computer Science Symposium in Russia, pp. 409\u2013424 (2016)","DOI":"10.1007\/978-3-319-34171-2_29"},{"issue":"26\u201328","key":"28_CR36","doi-asserted-by":"publisher","first-page":"2612","DOI":"10.1016\/j.tcs.2010.03.027","volume":"411","author":"Z Zhang","year":"2010","unstructured":"Zhang, Z., Shi, Y.: On the parity complexity measures of Boolean functions. Theoret. Comput. Sci. 411(26\u201328), 2612\u20132618 (2010)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:25:24Z","timestamp":1623972324000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}