{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:52:57Z","timestamp":1764132777998,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1145\/2488608.2488692","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"655-664","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Statistical algorithms and a lower bound for detecting planted cliques"],"prefix":"10.1145","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[{"name":"Almaden Research Center, IBM, San Jose, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lev","family":"Reyzin","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Xiao","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250863"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.315014"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0459-x"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_1_5_1","first-page":"49","volume-title":"ICS","author":"Arora S.","year":"2010","unstructured":"S. Arora , B. Barak , M. Brunnermeier , and R. Ge . Computational complexity and information asymmetry in financial products (extended abstract) . In ICS , pages 49 -- 65 , 2010 . S. Arora, B. Barak, M. Brunnermeier, and R. Ge. Computational complexity and information asymmetry in financial products (extended abstract). In ICS, pages 49--65, 2010."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0388"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095150"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013833"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_31"},{"key":"e_1_3_2_1_13_1","first-page":"281","volume-title":"Proceedings of NIPS","author":"Chu C.","year":"2006","unstructured":"C. Chu , S. Kim , Y. Lin , Y. Yu , G. Bradski , A. Ng , and K. Olukotun . Map-reduce for machine learning on multicore . In Proceedings of NIPS , pages 281 -- 288 , 2006 . C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Ng, and K. Olukotun. Map-reduce for machine learning on multicore. In Proceedings of NIPS, pages 281--288, 2006."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973013.8"},{"issue":"1","key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the em algorithm","volume":"39","author":"Dempster A. P.","year":"1977","unstructured":"A. P. Dempster , N. M. Laird , and D. B. Rubin . Maximum likelihood from incomplete data via the em algorithm . Journal of the Royal Statistical Society, Series B , 39 ( 1 ): 1 -- 38 , 1977 . A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1--38, 1977.","journal-title":"Journal of the Royal Statistical Society, Series B"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0095-7"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873188"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2%3C195::AID-RSA5%3E3.0.CO;2-A"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240118X"},{"key":"e_1_3_2_1_21_1","first-page":"189","volume-title":"Proceedings of AofA","author":"Feige U.","year":"2010","unstructured":"U. Feige and D. Ron . Finding hidden cliques in linear time . In Proceedings of AofA , pages 189 -- 204 , 2010 . U. Feige and D. Ron. Finding hidden cliques in linear time. In Proceedings of AofA, pages 189--204, 2010."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.024"},{"key":"e_1_3_2_1_23_1","volume-title":"Statistical algorithms and a lower bound for detecting planted cliques. CoRR, abs\/1201.1214","author":"Feldman V.","year":"2012","unstructured":"V. Feldman , E. Grigorescu , L. Reyzin , S. Vempala , and Y. Xiao . Statistical algorithms and a lower bound for detecting planted cliques. CoRR, abs\/1201.1214 , 2012 . V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. CoRR, abs\/1201.1214, 2012."},{"key":"e_1_3_2_1_24_1","first-page":"187","volume-title":"FSTTCS","author":"Frieze A. M.","year":"2008","unstructured":"A. M. Frieze and R. Kannan . A new approach to the planted clique problem . In FSTTCS , pages 187 -- 198 , 2008 . A. M. Frieze and R. Kannan. A new approach to the planted clique problem. In FSTTCS, pages 187--198, 2008."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10476213"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766991"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024697502780"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008374125234"},{"key":"e_1_3_2_1_32_1","unstructured":"R. Kannan. personal communication. R. Kannan. personal communication."},{"key":"e_1_3_2_1_33_1","first-page":"173","volume-title":"Proceedings of Computer Science and Statistics 12th Annual Symposium on the Interface","author":"Karp R.","year":"1979","unstructured":"R. Karp . Probabilistic analysis of graph-theoretic algorithms . In Proceedings of Computer Science and Statistics 12th Annual Symposium on the Interface , page 173 , 1979 . R. Karp. Probabilistic analysis of graph-theoretic algorithms. In Proceedings of Computer Science and Statistics 12th Annual Symposium on the Interface, page 173, 1979."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.59"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875554"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_50"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786440009463897"},{"key":"e_1_3_2_1_42_1","first-page":"521","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Selman B.","year":"1995","unstructured":"B. Selman , H. Kautz , and B. Cohen . Local search strategies for satisfiability testing . In DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pages 521 -- 532 , 1995 . B. Selman, H. Kautz, and B. Cohen. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 521--532, 1995."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1666"},{"key":"e_1_3_2_1_44_1","first-page":"186","volume-title":"ALT","author":"Sz\u00f6r\u00e9nyi B.","year":"2009","unstructured":"B. Sz\u00f6r\u00e9nyi . Characterizing statistical query learning: Simplified notions and proofs . In ALT , pages 186 -- 200 , 2009 . B. Sz\u00f6r\u00e9nyi. Characterizing statistical query learning: Simplified notions and proofs. In ALT, pages 186--200, 2009."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1987.10478458"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940812"},{"key":"e_1_3_2_1_49_1","first-page":"59","volume-title":"Proceedings of ALT","author":"Yang K.","year":"2001","unstructured":"K. Yang . On learning correlated boolean functions using statistical queries . In Proceedings of ALT , pages 59 -- 76 , 2001 . K. Yang. On learning correlated boolean functions using statistical queries. In Proceedings of ALT, pages 59--76, 2001."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.003"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Palo Alto California USA","acronym":"STOC'13"},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:20Z","timestamp":1750235960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":51,"alternative-id":["10.1145\/2488608.2488692","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488692","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}