{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:44:23Z","timestamp":1758278663556},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,4,5]],"date-time":"2017-04-05T00:00:00Z","timestamp":1491350400000},"content-version":"unspecified","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,6]]},"DOI":"10.1007\/s00037-017-0153-3","type":"journal-article","created":{"date-parts":[[2017,4,5]],"date-time":"2017-04-05T16:31:15Z","timestamp":1491409875000},"page":"323-364","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Block-symmetric polynomials correlate with parity better than symmetric"],"prefix":"10.1007","volume":"26","author":[{"given":"Frederic","family":"Green","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Kreymer","sequence":"additional","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,5]]},"reference":[{"key":"153_CR1","doi-asserted-by":"publisher","unstructured":"Scott Aaronson & Avi Wigderson (2008). Algebrization: a new barrier in complexity theory. In 40th ACM Symp. on the Theory of Computing (STOC), 731\u2013740.","DOI":"10.1145\/1374376.1374481"},{"key":"153_CR2","unstructured":"Noga Alon & Richard Beigel (2001). Lower bounds for approximations by low degree polynomials over Z\n                    \n                        m\n                    . In IEEE Conf. on Computational Complexity (CCC), 184\u2013187."},{"key":"153_CR3","first-page":"64","volume":"101","author":"Amano Kazuyuki","year":"2010","unstructured":"Kazuyuki Amano (2010) Researching the Complexity of Boolean Functions with Computers. Bulletin of the EATCS 101: 64\u201391","journal-title":"Bulletin of the EATCS"},{"key":"153_CR4","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Babai, Noam Nisan & M\u00e1ri\u00f3 Szegedy (1992). Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. of Computer and System Sciences 45(2), 204\u2013232. ISSN 0022-0000.","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"153_CR5","doi-asserted-by":"publisher","unstructured":"Theodore Baker, John Gill & Robert Solovay (1975). Relativizations of the P=?NP question. SIAM J. Comput. 4(4), 431\u2013442. ISSN 1095-7111.","DOI":"10.1137\/0204037"},{"issue":"2","key":"153_CR6","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1016\/j.jcss.2005.06.007","volume":"72","author":"Bhatnagar Nayantara","year":"2006","unstructured":"Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton (2006) -symmetric polynomials over Z\n                    \n                        m\n                     and simultaneous communication protocols. J. of Computer and System Sciences 72(2): 252\u2013285","journal-title":"J. of Computer and System Sciences"},{"key":"153_CR7","unstructured":"Joppe Bos & Marcelo Kaihara (2010). PlayStation 3 computing breaks 260 barrier: 112-bit prime ECDLP solved."},{"key":"153_CR8","doi-asserted-by":"publisher","unstructured":"Jean Bourgain (2005). Estimation of certain exponential sums arising in complexity theory. C. R. Math. Acad. Sci. Paris 340(9), 627\u2013631. ISSN 1631-073X.","DOI":"10.1016\/j.crma.2005.03.008"},{"issue":"3","key":"153_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF01201278","volume":"29","author":"Cai Jin-Yi","year":"1996","unstructured":"Jin-Yi Cai, Frederic Green, Thomas Thierauf (1996) On the Correlation of Symmetric Functions. Mathematical Systems Theory 29(3): 245\u2013258","journal-title":"Mathematical Systems Theory"},{"key":"153_CR10","doi-asserted-by":"publisher","unstructured":"Eduardo Due\u00f1ez, Steven J. Miller, Amitabha Roy & Howard Straubing (2006). Incomplete quadratic exponential sums in several variables. J. Number Theory 116(1), 168\u2013199. ISSN 0022-314X.","DOI":"10.1016\/j.jnt.2005.04.005"},{"issue":"4","key":"153_CR11","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s002240000126","volume":"32","author":"Green Frederic","year":"1999","unstructured":"Frederic Green (1999) Exponential Sums and Circuits with a Single Threshold Gate and Mod-Gates. Theory Comput. Syst. 32(4): 453\u2013466","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"153_CR12","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.jcss.2004.01.003","volume":"69","author":"Green Frederic","year":"2004","unstructured":"Frederic Green (2004) The correlation between parity and quadratic polynomials mod 3. J. of Computer and System Sciences 69(1): 28\u201344","journal-title":"J. of Computer and System Sciences"},{"key":"153_CR13","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1016\/j.jnt.2009.08.016","volume":"130","author":"Green Frederic","year":"2010","unstructured":"Frederic Green, Amitabha Roy (2010) Uniqueness of Optimal Mod 3 Circuits for Parity. Journal of Number Theory 130: 961\u2013975","journal-title":"Journal of Number Theory"},{"key":"153_CR14","doi-asserted-by":"publisher","unstructured":"Frederic Green, Amitabha Roy & Howard Straubing (2005). Bounds on an exponential sum arising in Boolean circuit complexity. C. R. Math. Acad. Sci. Paris 341(5), 279\u2013282. ISSN 1631-073X.","DOI":"10.1016\/j.crma.2005.07.011"},{"key":"153_CR15","unstructured":"Stanislaw Radziszowski (2014). Small Ramsey Numbers. The Electronic Journal of Combinatorics Dynamic Surveys, DS1.14, 1\u201394."},{"key":"153_CR16","unstructured":"Alexander Razborov (1987). Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki 41(4), 598\u2013607. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987."},{"issue":"1","key":"153_CR17","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"Razborov Alexander","year":"1997","unstructured":"Alexander Razborov, Steven Rudich (1997) Natural Proofs. J. of Computer and System Sciences 55(1): 24\u201335","journal-title":"J. of Computer and System Sciences"},{"key":"153_CR18","doi-asserted-by":"publisher","unstructured":"Roman Smolensky (1987). Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In 19th ACM Symp. on the Theory of Computing (STOC), 77\u201382. ACM.","DOI":"10.1145\/28395.28404"},{"key":"153_CR19","doi-asserted-by":"publisher","unstructured":"Roman Smolensky (1993). On Representations by Low-Degree Polynomials. In 34th IEEE IEEE Symp. on Foundations of Computer Science (FOCS), 130\u2013138.","DOI":"10.1109\/SFCS.1993.366874"},{"issue":"1","key":"153_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000033","volume":"5","author":"Viola Emanuele","year":"2009","unstructured":"Emanuele Viola (2009) On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science 5(1): 1\u201372","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"153_CR21","unstructured":"Emanuele Viola (2013). Challenges in computational lower bounds. Available at \n                        http:\/\/www.ccs.neu.edu\/home\/viola\/\n                        \n                    ."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0153-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0153-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0153-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,2]],"date-time":"2017-05-02T17:28:42Z","timestamp":1493746122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0153-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,5]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["153"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0153-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,5]]}}}