{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:46:25Z","timestamp":1764557185093,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374426","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"345-354","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["On hardness of learning intersection of two halfspaces"],"prefix":"10.1145","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[{"name":"NYU, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rishi","family":"Saket","sequence":"additional","affiliation":[{"name":"Georgia Tech, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"338","volume":"330","author":"Blum A.","year":"1996","unstructured":"A. Blum and A. Frieze and R. Kannan and S. Vempala . A Polynomial--Time Algorithm for Learning Noisy Linear Threshold Functions, Proc. 37th IEEE FOCS , 1996 , 330 -- 338 . A. Blum and A. Frieze and R. Kannan and S. Vempala. A Polynomial--Time Algorithm for Learning Noisy Linear Threshold Functions, Proc. 37th IEEE FOCS, 1996, 330--338.","journal-title":"37th IEEE FOCS"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.13"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1475"},{"key":"e_1_3_2_1_4_1","first-page":"513","volume":"508","author":"Vempala S.","year":"1997","unstructured":"S. Vempala , A Random Sampling Based Algorithm for Learning the Intersection of Half--spaces, Proc. 38th IEEE FOCS , 1997 , 508 -- 513 . S. Vempala, A Random Sampling Based Algorithm for Learning the Intersection of Half--spaces, Proc. 38th IEEE FOCS, 1997, 508--513.","journal-title":"IEEE FOCS"},{"key":"e_1_3_2_1_5_1","first-page":"186","volume":"177","author":"Klivans A.","year":"2002","unstructured":"A. Klivans and R. O'Donnell and R. Servedio , Learning Intersections and Thresholds of Halfspaces, Proc. 43rd IEEE FOCS , 2002 , 177 -- 186 . A. Klivans and R. O'Donnell and R. Servedio, Learning Intersections and Thresholds of Halfspaces, Proc. 43rd IEEE FOCS, 2002, 177--186.","journal-title":"Learning Intersections and Thresholds of Halfspaces, Proc. 43rd IEEE FOCS"},{"key":"e_1_3_2_1_6_1","first-page":"362","volume":"348","author":"Klivans A.","year":"2004","unstructured":"A. Klivans and R. Servedio , Learning Intersections of Halfspaces with a Margin, Proc. COLT , 2004 , 348 -- 362 . A. Klivans and R. Servedio, Learning Intersections of Halfspaces with a Margin, Proc. COLT, 2004, 348--362.","journal-title":"Learning Intersections of Halfspaces with a Margin, Proc. COLT"},{"key":"e_1_3_2_1_7_1","first-page":"623","volume":"616","author":"Arriaga R.","year":"1999","unstructured":"R. Arriaga and S. Vempala , An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proc. 40th IEEE FOCS , 1999 , 616 -- 623 . R. Arriaga and S. Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proc. 40th IEEE FOCS, 1999, 616--623.","journal-title":"40th IEEE FOCS"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.33"},{"key":"e_1_3_2_1_10_1","first-page":"28","volume":"9","author":"Blum A.","year":"1993","unstructured":"A. Blum and R. Rivest , Training a 3--Node Neural Network is NP--Complete, Proc. Machine Learning: From Theory to Applications , 1993 , 9 -- 28 . A. Blum and R. Rivest, Training a 3--Node Neural Network is NP--Complete, Proc. Machine Learning: From Theory to Applications, 1993, 9--28.","journal-title":"Training a 3--Node Neural Network is NP--Complete, Proc. Machine Learning: From Theory to Applications"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.36"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.24"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.31"},{"key":"e_1_3_2_1_14_1","first-page":"32","volume":"23","author":"Khot S.","year":"2002","unstructured":"S. Khot , Hardness Results for Coloring 3--Colorable 3--Uniform Hypergraphs, Proc. 43rd IEEE FOCS , 2002 , 23 -- 32 . S. Khot, Hardness Results for Coloring 3--Colorable 3--Uniform Hypergraphs, Proc. 43rd IEEE FOCS, 2002, 23--32.","journal-title":"IEEE FOCS"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007362"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.5"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_1_21_1","first-page":"650","volume":"635","author":"Levin A.","year":"2002","unstructured":"A. Levin and A. Shashua , Principal Component Analysis over Continuous Subspaces and Intersection of Half--Spaces, Proc. ECCCV(3) , 2002 , 635 -- 650 . A. Levin and A. Shashua, Principal Component Analysis over Continuous Subspaces and Intersection of Half--Spaces, Proc. ECCCV(3), 2002, 635--650.","journal-title":"ECCCV(3)"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(94)00066-K"},{"key":"e_1_3_2_1_23_1","first-page":"510","volume":"507","author":"Quantitative Association Rules Based on Half--Spaces: An Optimization Approach","year":"2004","unstructured":"Ulrich Ruckert and Lothar Richter and Stefan Kramer, Quantitative Association Rules Based on Half--Spaces: An Optimization Approach , Proc. ICDM , 2004 , 507 -- 510 . Ulrich Ruckert and Lothar Richter and Stefan Kramer, Quantitative Association Rules Based on Half--Spaces: An Optimization Approach, Proc. ICDM, 2004, 507--510.","journal-title":"Proc. ICDM"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022648800760"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Victoria British Columbia Canada","acronym":"STOC '08"},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:49Z","timestamp":1750255069000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":26,"alternative-id":["10.1145\/1374376.1374426","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374426","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}