{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:04:27Z","timestamp":1725563067054},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_44","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"588-601","source":"Crossref","is-referenced-by-count":6,"title":["Learning and Lower Bounds for AC 0 with Threshold Gates"],"prefix":"10.1007","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"44_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01215346","volume":"14","author":"J. Aspnes","year":"1994","unstructured":"Aspnes, J., Beigel, R., Furst, M., Rudich, S.: The expressive power of voting polynomials. Combinatorica\u00a014(2), 1\u201314 (1994)","journal-title":"Combinatorica"},{"key":"44_CR2","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/BF01263420","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R.: When do extra majority gates help? polylog(n) majority gates are equivalent to one. Computational Complexity\u00a04, 314\u2013324 (1994)","journal-title":"Computational Complexity"},{"unstructured":"Blais, E., O\u2019Donnell, R., Wimmer, K.: Polynomial regression under arbitrary product distributions. In: COLT, pp. 193\u2013204 (2008)","key":"44_CR3"},{"issue":"2","key":"44_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R. Beigel","year":"1995","unstructured":"Beigel, R., Reingold, N., Spielman, D.: PP is closed under intersection. Journal of Computer & System Sciences\u00a050(2), 191\u2013202 (1995)","journal-title":"Journal of Computer & System Sciences"},{"issue":"4","key":"44_CR5","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Tamon, C.: On the Fourier spectrum of monotone functions. Journal of the ACM\u00a043(4), 747\u2013770 (1996)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R., Wan, A.: Testing for concise representations. In: FOCS, pp. 549\u2013558 (2007)","key":"44_CR6","DOI":"10.1109\/FOCS.2007.32"},{"unstructured":"Diakonikolas, I., Raghavendra, P., Servedio, R., Tan, L.-Y.: Average sensitivity and noise sensitivity of polynomial threshold functions (2009), http:\/\/arxiv.org\/abs\/0909.5011","key":"44_CR7"},{"doi-asserted-by":"crossref","unstructured":"Furst, M., Jackson, J., Smith, S.: Improved learning of AC 0 functions. In: COLT, pp. 317\u2013325 (1991)","key":"44_CR8","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"issue":"1","key":"44_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jcss.2008.07.006","volume":"75","author":"L. Fortnow","year":"2009","unstructured":"Fortnow, L., Klivans, A.: Efficient learning algorithms yield circuit lower bounds. Journal of Computer & System Sciences\u00a075(1), 27\u201336 (2009)","journal-title":"Journal of Computer & System Sciences"},{"key":"44_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M. Goldmann","year":"1992","unstructured":"Goldmann, M., H\u00e5stad, J., Razborov, A.: Majority gates vs. general weighted threshold gates. Computational Complexity\u00a02, 277\u2013300 (1992)","journal-title":"Computational Complexity"},{"issue":"1","key":"44_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF01305949","volume":"14","author":"C. Gotsman","year":"1994","unstructured":"Gotsman, C., Linial, N.: Spectral properties of threshold functions. Combinatorica\u00a014(1), 35\u201350 (1994)","journal-title":"Combinatorica"},{"issue":"6","key":"44_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0020-0190(97)00141-5","volume":"63","author":"M. Goldmann","year":"1997","unstructured":"Goldmann, M.: On the power of a threshold gate at the top. Information Processing Letters\u00a063(6), 287\u2013293 (1997)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Gopalan, P., Servedio, R.A.: Learning and Lower Bounds for AC 0 with Threshold Gates (2010), http:\/\/eccc.hpi-web.de\/report\/2010\/074\/","key":"44_CR13","DOI":"10.1007\/978-3-642-15369-3_44"},{"doi-asserted-by":"crossref","unstructured":"Hansen, K.: Computing symmetric Boolean functions by circuits with few exact threshold gates. In: COCOON, pp. 448\u2013458 (2007)","key":"44_CR14","DOI":"10.1007\/978-3-540-73545-8_44"},{"key":"44_CR15","volume-title":"Computational Limitations for Small Depth Circuits","author":"J. H\u00e5stad","year":"1986","unstructured":"H\u00e5stad, J.: Computational Limitations for Small Depth Circuits. MIT Press, Cambridge (1986)"},{"issue":"3","key":"44_CR16","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1006\/jcss.2001.1803","volume":"63","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: A slight sharpening of LMN. Journal of Computer and System Sciences\u00a063(3), 498\u2013508 (2001)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Harsha, P., Klivans, A., Meka, R.: Bounding the sensitivity of polynomial threshold functions (2009), http:\/\/arxiv.org\/abs\/0909.5175","key":"44_CR17"},{"doi-asserted-by":"crossref","unstructured":"Jackson, J., Klivans, A., Servedio, R.: Learnability beyond AC 0. In: STOC, pp. 776\u2013784 (2002)","key":"44_CR18","DOI":"10.1145\/509907.510018"},{"issue":"6","key":"44_CR19","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1137\/060649057","volume":"37","author":"A. Kalai","year":"2008","unstructured":"Kalai, A., Klivans, A., Mansour, Y., Servedio, R.: Agnostically learning halfspaces. SIAM Journal on Computing\u00a037(6), 1777\u20131805 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"44_CR20","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/j.jcss.2003.11.002","volume":"68","author":"A. Klivans","year":"2004","unstructured":"Klivans, A., O\u2019Donnell, R., Servedio, R.: Learning intersections and thresholds of halfspaces. Journal of Computer & System Sciences\u00a068(4), 808\u2013840 (2004)","journal-title":"Journal of Computer & System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Klivans, A., O\u2019Donnell, R., Servedio, R.: Learning geometric concepts via Gaussian surface area. In: FOCS, pp. 541\u2013550 (2008)","key":"44_CR21","DOI":"10.1109\/FOCS.2008.64"},{"issue":"3","key":"44_CR22","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform and learnability. Journal of the ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"Journal of the ACM"},{"issue":"3","key":"44_CR23","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"E. Mossel","year":"2004","unstructured":"Mossel, E., O\u2019Donnell, R., Servedio, R.: Learning functions of k relevant variables. Journal of Computer & System Sciences\u00a069(3), 421\u2013434 (2004)","journal-title":"Journal of Computer & System Sciences"},{"issue":"3","key":"44_CR24","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/060669309","volume":"37","author":"R. O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Servedio, R.: Learning monotone decision trees in polynomial time. SIAM J. Comput.\u00a037(3), 827\u2013844 (2007)","journal-title":"SIAM J. Comput."},{"unstructured":"Podolskii, V.: Personal communication (2010)","key":"44_CR25"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.: The intersection of two halfspaces has high threshold degree. In: FOCS, pp. 343\u2013362 (2009)","key":"44_CR26","DOI":"10.1109\/FOCS.2009.18"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:31Z","timestamp":1606187131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}