{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T10:56:49Z","timestamp":1780916209314,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,2]],"date-time":"2015-09-02T00:00:00Z","timestamp":1441152000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00037-015-0110-y","type":"journal-article","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T06:48:07Z","timestamp":1441090087000},"page":"229-273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["On the Structure of Boolean Functions with Small Spectral Norm"],"prefix":"10.1007","volume":"26","author":[{"given":"Amir","family":"Shpilka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ben lee","family":"Volk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,9,2]]},"reference":[{"issue":"1","key":"110_CR1","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jcss.2007.04.011","volume":"74","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich M., Braverman M., Feldman V., Klivans A.R., Pitassi T. (2008) The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. 74(1): 16\u201334","journal-title":"J. Comput. Syst. Sci."},{"key":"110_CR2","doi-asserted-by":"crossref","unstructured":"M. Bellare (1992). A Technique for Upper Bounding the Spectral Norm with Applications to Learning. In Proceedings of the 5th Annual COLT, 62\u201370.","DOI":"10.1145\/130385.130392"},{"issue":"6","key":"110_CR3","doi-asserted-by":"crossref","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M. Bellare","year":"1996","unstructured":"Bellare M., Coppersmith D., H\u00e5stad J., Kiwi M.A., Sudan M. (1996) Linearity testing in characteristic two. IEEE Trans. Inf. Theory. 42(6): 1781\u20131795","journal-title":"IEEE Trans. Inf. Theory."},{"issue":"3","key":"110_CR4","doi-asserted-by":"crossref","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. (1993) Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3): 549\u2013595","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"110_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H. Buhrman","year":"2002","unstructured":"Buhrman H., de Wolf R. (2002) Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1): 21\u201343","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"110_CR6","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E. Friedgut","year":"1998","unstructured":"Friedgut E. (1998) Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18(1): 27\u201335","journal-title":"Combinatorica"},{"key":"110_CR7","unstructured":"O. Goldreich & L. A. Levin (1989). A hardcore predicate for all one-way functions. In Proceedings of the 21st STOC, 25\u201332."},{"issue":"4","key":"110_CR8","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., Wimmer K. (2011) Testing Fourier dimensionality and sparsity. SIAM J. Comput. 40(4): 1075\u20131100","journal-title":"SIAM J. Comput."},{"key":"110_CR9","first-page":"144","volume":"18","author":"B. Green","year":"2008","unstructured":"Green B., Sanders T. (2008a) Boolean functions with small spectral norm. GAFA 18: 144\u2013162","journal-title":"GAFA"},{"issue":"3","key":"110_CR10","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.4007\/annals.2008.168.1025","volume":"168","author":"B. Green","year":"2008","unstructured":"Green B., Sanders T. (2008b) A quantitative version of the idempotent theorem in harmonic analysis. Annals of Math. 168(3): 1025\u20131054","journal-title":"Annals of Math."},{"issue":"1","key":"110_CR11","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0304-3975(96)00290-3","volume":"188","author":"V. Grolmusz","year":"1997","unstructured":"Grolmusz V. (1997) On the power of circuits with gates of low L 1 norms. Theor. Comput. Sci. 188(1): 117\u2013128","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"110_CR12","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J. (2001) Some optimal inapproximability results. J. ACM 48(4): 798\u2013859","journal-title":"J. ACM"},{"key":"110_CR13","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai & N. Linial (1988). The influence of variables on Boolean functions. In Proceedings of the 29th annual FOCS, 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"issue":"3","key":"110_CR14","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/S0196-8858(02)00023-4","volume":"29","author":"G. Kalai","year":"2002","unstructured":"Kalai G. (2002) A Fourier-theoretic perspective on the Condorcet paradox and Arrow\u2019s theorem. Adv. Appl. Math. 29(3): 412\u2013426","journal-title":"Adv. Appl. Math."},{"issue":"6","key":"110_CR15","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"Kushilevitz E., Mansour Y. (1993) Learning Decision Trees Using the Fourier Spectrum. SIAM J. Comput. 22(6): 1331\u20131348","journal-title":"SIAM J. Comput."},{"issue":"3","key":"110_CR16","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial N., Mansour Y., Nisan N. (1993) Constant Depth Circuits, Fourier Transform and Learnability. J. ACM 40(3): 607\u2013620","journal-title":"J. ACM"},{"key":"110_CR17","doi-asserted-by":"crossref","unstructured":"S. Lovett (2014). Communication is bounded by root of rank. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC).","DOI":"10.1145\/2591796.2591799"},{"key":"110_CR18","doi-asserted-by":"crossref","unstructured":"Y. Mansour (1994). Learning Boolean functions via the Fourier transform. In Theoretical advances in neural computation and learning, 391\u2013424.","DOI":"10.1007\/978-1-4615-2696-4_11"},{"key":"110_CR19","unstructured":"A. Montanaro & T. Osborne (2009). On the communication complexity of XOR functions. CoRR abs\/0909.3392."},{"key":"110_CR20","doi-asserted-by":"crossref","unstructured":"R. O\u2019Donnell (2014). Analysis of boolean functions. Cambridge University Press.","DOI":"10.1017\/CBO9781139814782"},{"key":"110_CR21","doi-asserted-by":"crossref","unstructured":"A. Shpilka, A. Tal & B. L. Volk (2014). On the structure of boolean functions with small spectral norm. In Innovations in Theoretical Computer Science, ITCS\u201914, 37\u201348.","DOI":"10.1145\/2554797.2554803"},{"key":"110_CR22","unstructured":"P. M. Spira (1971). On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th HICSS, 525\u2013527."},{"key":"110_CR23","doi-asserted-by":"crossref","unstructured":"H. Y. Tsang, C. H. Wong, N. Xie & S. Zhang (2013). Fourier sparsity, spectral norm, and the Log-rank conjecture. In Proceedings of the 54th Annual FOCS, 658\u2013667.","DOI":"10.1109\/FOCS.2013.76"},{"key":"110_CR24","unstructured":"S. V. Yablonskii (1954). Realization of the linear function in the class of $${\\Pi}$$ \u03a0 -schemes. In Dokl. Akad. Nauk SSSR, volume 94, 805\u2013806. In Russian."},{"key":"110_CR25","doi-asserted-by":"crossref","unstructured":"Z. Zhang & Y. Shi (2010). On the parity complexity measures of Boolean functions. Theor. Comput. Sci. 411(26-28), 2612 \u2013 2618. ISSN 0304-3975.","DOI":"10.1016\/j.tcs.2010.03.027"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0110-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0110-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0110-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0110-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0110-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,2]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["110"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0110-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,2]]}}}