{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T15:10:06Z","timestamp":1748790606904,"version":"3.41.0"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319299990"},{"type":"electronic","value":"9783319300009"}],"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-30000-9_20","type":"book-chapter","created":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T21:45:50Z","timestamp":1456436750000},"page":"259-269","source":"Crossref","is-referenced-by-count":0,"title":["On XOR Lemma for Polynomial Threshold Weight and Length"],"prefix":"10.1007","author":[{"given":"Kazuyuki","family":"Amano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,2,26]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/978-3-642-17517-6_28","volume-title":"Algorithms and Computation","author":"K Amano","year":"2010","unstructured":"Amano, K.: New upper bounds on the average PTF density of boolean functions. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol. 6506, pp. 304\u2013315. Springer, Heidelberg (2010)"},{"doi-asserted-by":"crossref","unstructured":"Beigel, R.: The polynomial method in circuit complexity. In: Proceedings of 8th Conference on Structure in Complexity Theory, pp. 82\u201395 (1993)","key":"20_CR2","DOI":"10.1109\/SCT.1993.336538"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J Bruck","year":"1990","unstructured":"Bruck, J.: Harmonic analysis of polynomial threshold functions. SIAM J. Disc. Math. 3(2), 168\u2013177 (1990)","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J Bruck","year":"1992","unstructured":"Bruck, J., Smolensky, R.: Polynomial threshold functions, AC $$^0$$ 0 functions, and spectral norms. SIAM J. Comput. 21(1), 33\u201342 (1992)","journal-title":"SIAM J. Comput."},{"unstructured":"Filmus, Y., Hatami, H., Heilman, S., Mossel, E., O\u2019Donnell, R., Sachdeva, S., Wan, A., Wimmer, K.: Real analysis in computer science: a collection of open problems (2014). https:\/\/simons.berkeley.edu\/sites\/default\/files\/openprobsmerged.pdf","key":"20_CR5"},{"issue":"4","key":"20_CR6","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/j.jcss.2003.11.002","volume":"68","author":"AR Klivans","year":"2004","unstructured":"Klivans, A.R., O\u2019Donnell, R., Servedio, R.A.: Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci. 68(4), 808\u2013840 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"AR Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Learning DNF in time $$2^{\\tilde{o}(n^{1\/3})}$$ 2 o ~ ( n 1 \/ 3 ) time. J. Comput. Syst. Sci. 68(2), 303\u2013318 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"20_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10994-007-5010-1","volume":"69","author":"AR Klivans","year":"2007","unstructured":"Klivans, A.R., Sherstov, A.A.: Unconditional lower bounds for learning intersections of halfspaces. Mach. Learn. 69(2\u20133), 97\u2013114 (2007)","journal-title":"Mach. Learn."},{"key":"20_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, New York (2005)"},{"key":"20_CR10","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":"3","key":"20_CR11","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00493-010-2173-3","volume":"30","author":"R O\u2019Donnell","year":"2010","unstructured":"O\u2019Donnell, R., Servedio, R.A.: New degree bounds for polynomial threshold functions. Combinatorica 30(3), 327\u2013358 (2010)","journal-title":"Combinatorica"},{"issue":"1","key":"20_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1137\/0405011","volume":"5","author":"R Pemantle","year":"1992","unstructured":"Pemantle, R., Propp, J.G., Ullman, D.: On tensor powers of integer programs. SIAM J. Disc. Math. 5(1), 127\u2013143 (1992)","journal-title":"SIAM J. Disc. Math."},{"doi-asserted-by":"crossref","unstructured":"Saks, M.E.: Slicing the hypercubes. In: Surveys in Combinatorics, pp. 211\u2013255 (1993)","key":"20_CR13","DOI":"10.1017\/CBO9780511662089.009"},{"issue":"8","key":"20_CR14","doi-asserted-by":"publisher","first-page":"1796","DOI":"10.1162\/NECO_a_00750","volume":"27","author":"CE Sezener","year":"2015","unstructured":"Sezener, C.E., Oztop, E.: Minimal sign representation of boolean functions: algorithms and exact results for low dimensions. Neural Comput. 27(8), 1796\u20131823 (2015)","journal-title":"Neural Comput."},{"issue":"6","key":"20_CR15","doi-asserted-by":"publisher","first-page":"2329","DOI":"10.1137\/100785260","volume":"42","author":"AA Sherstov","year":"2013","unstructured":"Sherstov, A.A.: The intersection of two halfspaces has high threshold degree. SIAM J. Comput. 42(6), 2329\u20132374 (2013)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-30000-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T14:36:34Z","timestamp":1748788594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-30000-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319299990","9783319300009"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-30000-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}