{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:42Z","timestamp":1775282322913,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s00493-013-2759-7","type":"journal-article","created":{"date-parts":[[2013,6,22]],"date-time":"2013-06-22T09:46:53Z","timestamp":1371894413000},"page":"73-96","source":"Crossref","is-referenced-by-count":16,"title":["Optimal bounds for sign-representing the intersection of two halfspaces by polynomials"],"prefix":"10.1007","volume":"33","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,6,23]]},"reference":[{"issue":"1","key":"2759_CR1","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jcss.2007.04.011","volume":"74","author":"M Alekhnovich","year":"2008","unstructured":"M. Alekhnovich, M. Braverman, V. Feldman, A. R. Klivans and T. Pitassi: The complexity of properly learning simple concept classes, J. Comput. Syst. Sci. 74(1) (2008), 16\u201334.","journal-title":"J. Comput. Syst. Sci."},{"key":"2759_CR2","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/FOCS.2007.57","volume-title":"Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"A Ambainis","year":"2007","unstructured":"A. Ambainis, A. M. Childs, B. Reichardt, R. \u0160palek and S. Zhang: Any AND-OR formula of size N can be evaluated in time N 1\/2+o(1) on a quantum computer, In: Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 363\u2013372, 2007."},{"issue":"2","key":"2759_CR3","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s10994-006-6265-7","volume":"63","author":"R I Arriaga","year":"2006","unstructured":"R. I. Arriaga and S. Vempala: An algorithmic theory of learning: Robust concepts and random projection, Mach. Learn. 63(2) (2006), 161\u2013182.","journal-title":"Mach. Learn."},{"issue":"2","key":"2759_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF01215346","volume":"14","author":"J Aspnes","year":"1994","unstructured":"J. Aspnes, R. Beigel, M. L. Furst and S. Rudich: The expressive power of voting polynomials, Combinatorica 14(2) (1994), 135\u2013148.","journal-title":"Combinatorica"},{"key":"2759_CR5","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01263422","volume":"4","author":"R Beigel","year":"1994","unstructured":"R. Beigel: Perceptrons, PP, and the polynomial hierarchy, Computational Complexity 4 (1994), 339\u2013349.","journal-title":"Computational Complexity"},{"issue":"2","key":"2759_CR6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R Beigel","year":"1995","unstructured":"R. Beigel, N. Reingold and D. A. Spielman: PP is closed under intersection, J. Comput. Syst. Sci. 50(2) (1995), 191\u2013202.","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"2759_CR7","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1006\/jcss.1997.1475","volume":"54","author":"A Blum","year":"1997","unstructured":"A. Blum and R. Kannan: Learning an intersection of a constant number of halfspaces over a uniform distribution, J. Comput. Syst. Sci. 54(2) (1997), 371\u2013380.","journal-title":"J. Comput. Syst. Sci."},{"key":"2759_CR8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","volume":"5","author":"A L Blum","year":"1992","unstructured":"A. L. Blum and R. L. Rivest: Training a 3-node neural network is NP-complete, Neural Networks 5 (1992), 117\u2013127.","journal-title":"Neural Networks"},{"key":"2759_CR9","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/CCC.2007.18","volume-title":"Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity (CCC)","author":"H Buhrman","year":"2007","unstructured":"H. Buhrman, N. K. Vereshchagin and R. de Wolf: On computation and communication with small bias, In: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity (CCC), 24\u201332, 2007."},{"issue":"1","key":"2759_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.4086\/toc.2008.v004a008","volume":"4","author":"E Farhi","year":"2008","unstructured":"E. Farhi, J. Goldstone and S. Gutmann: A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing 4(1) (2008), 169\u2013190.","journal-title":"Theory of Computing"},{"key":"2759_CR11","first-page":"749","volume":"7","author":"S A Gershgorin","year":"1931","unstructured":"S. A. Gershgorin: Uber die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. U.S.S.R. Otd. Fiz.-Mat. Nauk 7 (1931), 749\u2013754.","journal-title":"Izv. Akad. Nauk. U.S.S.R. Otd. Fiz.-Mat. Nauk"},{"issue":"3","key":"2759_CR12","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J C Jackson","year":"1997","unstructured":"J. C. Jackson: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, J. Comput. Syst. Sci. 55(3) (1997), 414\u2013440.","journal-title":"J. Comput. Syst. Sci."},{"key":"2759_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal Combinatorics with Applications in Computer Science","author":"S Jukna","year":"2001","unstructured":"S. Jukna: Extremal Combinatorics with Applications in Computer Science, Springer-Verlag, Berlin, 2001."},{"key":"2759_CR14","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/1374376.1374426","volume-title":"Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC)","author":"S Khot","year":"2008","unstructured":"S. Khot and R. Saket: On hardness of learning intersection of two halfspaces, In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC), 345\u2013354, 2008."},{"key":"2759_CR15","volume-title":"A Complexity-Theoretic Approach to Learning","author":"A R Klivans","year":"2002","unstructured":"A. R. Klivans: A Complexity-Theoretic Approach to Learning, PhD thesis, MIT, 2002."},{"key":"2759_CR16","first-page":"588","volume-title":"Proceedings of the Thirteenth International Workshop on Randomization and Computation (RANDOM)","author":"A R Klivans","year":"2009","unstructured":"A. R. Klivans, P. M. Long and A. K. Tang: Baum\u2019s algorithm learns intersections of halfspaces with respect to log-concave distributions, In: Proceedings of the Thirteenth International Workshop on Randomization and Computation (RANDOM), 588\u2013600, 2009."},{"issue":"4","key":"2759_CR17","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1016\/j.jcss.2003.11.002","volume":"68","author":"A R Klivans","year":"2004","unstructured":"A. R. Klivans, R. O\u2019Donnell and R. A. Servedio: Learning intersections and thresholds of halfspaces, J. Comput. Syst. Sci. 68(4) (2004), 808\u2013840.","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"2759_CR18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"A R Klivans","year":"2004","unstructured":"A. R. Klivans and R. A. Servedio: Learning DNF in time {ie95-1}, J. Comput. Syst. Sci. 68(2) (2004), 303\u2013318.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2759_CR19","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.jcss.2007.04.012","volume":"74","author":"A R Klivans","year":"2008","unstructured":"A. R. Klivans and R. A. Servedio: Learning intersections of halfspaces with a margin, J. Comput. Syst. Sci. 74(1) (2008), 35\u201348.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2759_CR20","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jcss.2008.07.008","volume":"75","author":"A R Klivans","year":"2009","unstructured":"A. R. Klivans and A. A. Sherstov: Cryptographic hardness for learning intersections of halfspaces, J. Comput. Syst. Sci. 75(1) (2009), 2\u201312. Preliminary version in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"2759_CR21","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0304-3975(96)00019-9","volume":"174","author":"M Krause","year":"1997","unstructured":"M. Krause and P. Pudl\u00e1k: On the computational power of depth-2 circuits with threshold and modulo gates, Theor. Comput. Sci. 174(1\u20132) (1997), 137\u2013156.","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"2759_CR22","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/s000370050015","volume":"7","author":"M Krause","year":"1998","unstructured":"M. Krause and P. Pudl\u00e1k: Computing Boolean functions by polynomials and threshold circuits, Comput. Complex. 7(4) (1998), 346\u2013370.","journal-title":"Comput. Complex."},{"issue":"1\/2","key":"2759_CR23","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/PL00013834","volume":"22","author":"S Kwek","year":"1998","unstructured":"S. Kwek and L. Pitt: PAC learning intersections of halfspaces with membership queries, Algorithmica 22(1\/2) (1998), 53\u201375.","journal-title":"Algorithmica"},{"key":"2759_CR24","volume-title":"A note on the sign degree of formulas","author":"T Lee","year":"2009","unstructured":"T. Lee: A note on the sign degree of formulas, 2009. Available at http:\/\/arxiv.org\/abs\/0909.4607 ."},{"key":"2759_CR25","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"M L Minsky","year":"1969","unstructured":"M. L. Minsky and S. A. Papert: Perceptrons: An Introduction to Computational Geometry, MIT Press, Cambridge, Mass., 1969."},{"key":"2759_CR26","volume-title":"Threshold Logic and Its Applications","author":"S Muroga","year":"1971","unstructured":"S. Muroga: Threshold Logic and Its Applications, John Wiley & Sons, New York, 1971."},{"issue":"2","key":"2759_CR27","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1109\/TEC.1961.5219204","volume":"10","author":"J Myhill","year":"1961","unstructured":"J. Myhill and W. H. Kautz: On the size of weights required for linear-input switching functions, IRE Trans. on Electronic Computers 10(2) (1961), 288\u2013290.","journal-title":"IRE Trans. on Electronic Computers"},{"issue":"1","key":"2759_CR28","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1307\/mmj\/1028999029","volume":"11","author":"D J Newman","year":"1964","unstructured":"D. J. Newman: Rational approximation to |x|, Michigan Math. J. 11(1) (1964), 11\u201314.","journal-title":"Michigan Math. J."},{"key":"2759_CR29","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1145\/780542.780592","volume-title":"Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC)","author":"R O\u2019Donnell","year":"2003","unstructured":"R. O\u2019Donnell and R. A. Servedio: New degree bounds for polynomial threshold functions, In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC), 325\u2013334, 2003."},{"issue":"2","key":"2759_CR30","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1006\/inco.1994.1059","volume":"112","author":"R Paturi","year":"1994","unstructured":"R. Paturi and M. E. Saks: Approximating threshold circuits by rational functions, Inf. Comput. 112(2) (1994), 257\u2013272.","journal-title":"Inf. Comput."},{"issue":"5","key":"2759_CR31","doi-asserted-by":"crossref","first-page":"1833","DOI":"10.1137\/080744037","volume":"39","author":"A A Razborov","year":"2010","unstructured":"A. A. Razborov and A. A. Sherstov: The sign-rank of AC0, SIAM J. Comput. 39(5) (2010), 1833\u20131855. Preliminary version in Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008.","journal-title":"SIAM J. Comput."},{"key":"2759_CR32","volume-title":"An Introduction to the Approximation of Functions","author":"T J Rivlin","year":"1981","unstructured":"T. J. Rivlin: An Introduction to the Approximation of Functions, Dover Publications, New York, 1981."},{"key":"2759_CR33","first-page":"211","volume-title":"Surveys in Combinatorics","author":"M E Saks","year":"1993","unstructured":"M. E. Saks: Slicing the hypercube, Surveys in Combinatorics, 211\u2013255, 1993."},{"key":"2759_CR34","first-page":"343","volume-title":"Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"A A Sherstov","year":"2009","unstructured":"A. A. Sherstov: The intersection of two halfspaces has high threshold degree, In: Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 343\u2013362, 2009."},{"issue":"6","key":"2759_CR35","doi-asserted-by":"crossref","first-page":"2113","DOI":"10.1137\/08071421X","volume":"38","author":"A A Sherstov","year":"2009","unstructured":"A. A. Sherstov: Separating AC0 from depth-2 majority circuits, SIAM J. Comput. 38(6) (2009), 2113\u20132129. Preliminary version in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC), 2007.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"2759_CR36","doi-asserted-by":"crossref","first-page":"1969","DOI":"10.1137\/080733644","volume":"40","author":"A A Sherstov","year":"2011","unstructured":"A. A. Sherstov: The pattern matrix method, SIAM J. Comput. 40(6) (2011), 1969\u20132000. Preliminary version in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC), 2008.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"2759_CR37","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s00493-011-2580-0","volume":"31","author":"A A Sherstov","year":"2011","unstructured":"A. A. Sherstov: The unbounded-error communication complexity of symmetric functions, Combinatorica 31(5) (2011), 583\u2013614. Preliminary version in Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008.","journal-title":"Combinatorica"},{"issue":"3","key":"2759_CR38","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0404038","volume":"4","author":"K-Y Siu","year":"1991","unstructured":"K.-Y. Siu and J. Bruck: On the power of threshold circuits with small weights, SIAM J. Discrete Math. 4(3) (1991), 423\u2013435.","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"2759_CR39","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/18.312168","volume":"40","author":"K-Y Siu","year":"1994","unstructured":"K.-Y. Siu, V. P. Roychowdhury and T. Kailath: Rational approximation techniques for analysis of neural networks, IEEE Transactions on Information Theory 40(2) (1994), 455\u2013466.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"11","key":"2759_CR40","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L G Valiant","year":"1984","unstructured":"L. G. Valiant: A theory of the learnable, Commun. ACM 27(11) (1984), 1134\u20131142.","journal-title":"Commun. ACM"},{"key":"2759_CR41","first-page":"508","volume-title":"Proceedings of the Thirty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"S Vempala","year":"1997","unstructured":"S. Vempala: A random sampling based algorithm for learning the intersection of halfspaces, In: Proceedings of the Thirty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 508\u2013513, 1997."},{"key":"2759_CR42","unstructured":"E. I. Zolotarev: Application of elliptic functions to questions of functions deviating least and most from zero, Izvestiya Imp. Akad. Nauk 30(5), 1877."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-013-2759-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-013-2759-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-013-2759-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T01:32:49Z","timestamp":1559093569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-013-2759-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["2759"],"URL":"https:\/\/doi.org\/10.1007\/s00493-013-2759-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2]]}}}