{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:37:41Z","timestamp":1774679861818,"version":"3.50.1"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,15]],"date-time":"2017-04-15T00:00:00Z","timestamp":1492214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Computing Research Association for the CIFellows Project. Research, NSF","award":["CCF-0915903 and CCF-1217793"],"award-info":[{"award-number":["CCF-0915903 and CCF-1217793"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1019343"],"award-info":[{"award-number":["1019343"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Simons Postdoctoral Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a<jats:italic>statistical query<\/jats:italic>oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, for example, moments-based methods, local search, standard iterative methods for convex optimization, MCMC, and simulated annealing, can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory [Kearns 1998].<\/jats:p><jats:p>Our main application is a nearly optimal lower bound on the complexity of<jats:italic>any<\/jats:italic>statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>1\/2 \u2212 \u03b4<\/jats:sup>) for any constant \u03b4 &gt; 0. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.<\/jats:p>","DOI":"10.1145\/3046674","type":"journal-article","created":{"date-parts":[[2017,4,17]],"date-time":"2017-04-17T12:26:58Z","timestamp":1492432018000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Statistical Algorithms and a Lower Bound for Detecting Planted Cliques"],"prefix":"10.1145","volume":"64","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}]},{"given":"Lev","family":"Reyzin","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, Chicago, IL"}]},{"given":"Santosh S.","family":"Vempala","sequence":"additional","affiliation":[{"name":"Georgia Tech, Atlanta, GA"}]},{"given":"Ying","family":"Xiao","sequence":"additional","affiliation":[{"name":"Palantir Technologies"}]}],"member":"320","published-online":{"date-parts":[[2017,4,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250863"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.3.CO;2-K"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0459-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_2_1_5_1","unstructured":"Sanjeev Arora Boaz Barak Markus Brunnermeier and Rong Ge. 2010. Computational complexity and information asymmetry in financial products (extended abstract). In ICS. 49--65. Sanjeev Arora Boaz Barak Markus Brunnermeier and Rong Ge. 2010. Computational complexity and information asymmetry in financial products (extended abstract). In ICS. 49--65."},{"key":"e_1_2_1_6_1","first-page":"463","article-title":"Rademacher and gaussian Complexities: Risk Bounds and Structural Results","volume":"3","author":"Bartlett P.","year":"2002","unstructured":"P. Bartlett and S. Mendelson . 2002 . Rademacher and gaussian Complexities: Risk Bounds and Structural Results . J. Mach. Learn. Res. 3 (2002), 463 -- 482 . P. Bartlett and S. Mendelson. 2002. Rademacher and gaussian Complexities: Risk Bounds and Structural Results. J. Mach. Learn. Res. 3 (2002), 463--482.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0388"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1569"},{"key":"e_1_2_1_9_1","unstructured":"Quentin Berthet and Philippe Rigollet. 2013. Complexity theoretic lower bounds for sparse principal component detection. In COLT. 1046--1066. Quentin Berthet and Philippe Rigollet. 2013. Complexity theoretic lower bounds for sparse principal component detection. In COLT. 1046--1066."},{"key":"e_1_2_1_10_1","unstructured":"Aditya Bhaskara Moses Charikar Eden Chlamtac Uriel Feige and Aravindan Vijayaraghavan. 2010. Detecting high log-densities: An o(n1\/4) approximation for densest k-subgraph. In STOC. 201--210. Aditya Bhaskara Moses Charikar Eden Chlamtac Uriel Feige and Aravindan Vijayaraghavan. 2010. Detecting high log-densities: An o ( n 1\/4 ) approximation for densest k-subgraph. In STOC. 201--210."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Aditya Bhaskara Moses Charikar Aravindan Vijayaraghavan Venkatesan Guruswami and Yuan Zhou. 2012. Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In SODA. 388--405. Aditya Bhaskara Moses Charikar Aravindan Vijayaraghavan Venkatesan Guruswami and Yuan Zhou. 2012. Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In SODA. 388--405.","DOI":"10.1137\/1.9781611973099.34"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"A. Blum C. Dwork F. McSherry and K. Nissim. 2005. Practical privacy: The SuLQ framework. In PODS. 128--138. A. Blum C. Dwork F. McSherry and K. Nissim. 2005. Practical privacy: The SuLQ framework. In PODS. 128--138.","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013833"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_2_1_15_1","unstructured":"Guy Bresler David Gamarnik and Devavrat Shah. 2014. Structure learning of antiferromagnetic Ising models. In NIPS. 2852--2860. Guy Bresler David Gamarnik and Devavrat Shah. 2014. Structure learning of antiferromagnetic Ising models. In NIPS. 2852--2860."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_31"},{"key":"e_1_2_1_17_1","unstructured":"T. T. Cai T. Liang and A. Rakhlin. 2015. Computational and statistical boundaries for submatrix localization in a large noisy matrix. ArXiv E-prints (Feb. 2015). T. T. Cai T. Liang and A. Rakhlin. 2015. Computational and statistical boundaries for submatrix localization in a large noisy matrix. ArXiv E-prints (Feb. 2015)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"C. Chu S. Kim Y. Lin Y. Yu G. Bradski A. Ng and K. Olukotun. 2006. Map-reduce for machine learning on multicore. In NIPS. 281--288. C. Chu S. Kim Y. Lin Y. Yu G. Bradski A. Ng and K. Olukotun. 2006. Map-reduce for machine learning on multicore. In NIPS. 281--288.","DOI":"10.7551\/mitpress\/7503.003.0040"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973013.8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9215-y"},{"key":"e_1_2_1_23_1","unstructured":"Yash Deshpande and Andrea Montanari. 2015b. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In COLT. 523--562. Yash Deshpande and Andrea Montanari. 2015b. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In COLT. 523--562."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.45"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0095-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_2_1_27_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_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240118X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"U. Feige and D. Ron. 2010. Finding hidden cliques in linear time. In AofA. 189--204. U. Feige and D. Ron. 2010. Finding hidden cliques in linear time. In AofA. 189--204.","DOI":"10.46298\/dmtcs.2802"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374465"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.024"},{"key":"e_1_2_1_32_1","unstructured":"Vitaly Feldman. 2014. Open problem: The statistical query complexity of learning sparse halfspaces. In COLT. 1283--1289. Vitaly Feldman. 2014. Open problem: The statistical query complexity of learning sparse halfspaces. In COLT. 1283--1289."},{"key":"e_1_2_1_33_1","volume-title":"A general characterization of the statistical query complexity. CoRR abs\/1608.02198","author":"Feldman Vitaly","year":"2016","unstructured":"Vitaly Feldman . 2016. A general characterization of the statistical query complexity. CoRR abs\/1608.02198 ( 2016 ). Retrieved from http:\/\/arxiv.org\/abs\/1608.02198. Vitaly Feldman. 2016. A general characterization of the statistical query complexity. CoRR abs\/1608.02198 (2016). Retrieved from http:\/\/arxiv.org\/abs\/1608.02198."},{"key":"e_1_2_1_34_1","volume-title":"Statistical query algorithms for stochastic convex optimization. CoRR abs\/1512.09170","author":"Feldman Vitaly","year":"2015","unstructured":"Vitaly Feldman , Cristobal Guzman , and Santosh Vempala . 2015. Statistical query algorithms for stochastic convex optimization. CoRR abs\/1512.09170 ( 2015 ). Extended abstract in SODA 2017. Vitaly Feldman, Cristobal Guzman, and Santosh Vempala. 2015. Statistical query algorithms for stochastic convex optimization. CoRR abs\/1512.09170 (2015). Extended abstract in SODA 2017."},{"key":"e_1_2_1_35_1","volume-title":"On the complexity of random satisfiability problems with planted solutions. CoRR abs\/1311.4821","author":"Feldman Vitaly","year":"2013","unstructured":"Vitaly Feldman , Will Perkins , and Santosh Vempala . 2013. On the complexity of random satisfiability problems with planted solutions. CoRR abs\/1311.4821 ( 2013 ). Extended abstract in STOC 2015. Vitaly Feldman, Will Perkins, and Santosh Vempala. 2013. On the complexity of random satisfiability problems with planted solutions. CoRR abs\/1311.4821 (2013). Extended abstract in STOC 2015."},{"key":"e_1_2_1_36_1","volume-title":"Frieze and Ravi Kannan","author":"Alan","year":"2008","unstructured":"Alan M. Frieze and Ravi Kannan . 2008 . A new approach to the planted clique problem. In FSTTCS. 187--198. Alan M. Frieze and Ravi Kannan. 2008. A new approach to the planted clique problem. In FSTTCS. 187--198."},{"key":"e_1_2_1_37_1","unstructured":"C. Gao Z. Ma and H. H. Zhou. 2014. Sparse CCA: Adaptive estimation and computational barriers. ArXiv E-prints (Sept. 2014). C. Gao Z. Ma and H. H. Zhou. 2014. Sparse CCA: Adaptive estimation and computational barriers. ArXiv E-prints (Sept. 2014)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10476213"},{"key":"e_1_2_1_39_1","unstructured":"Bruce E. Hajek Yihong Wu and Jiaming Xu. 2015. Computational lower bounds for community detection on random graphs. In COLT. 899--928. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v40\/Hajek15.html. Bruce E. Hajek Yihong Wu and Jiaming Xu. 2015. Computational lower bounds for community detection on random graphs. In COLT. 899--928. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v40\/Hajek15.html."},{"key":"e_1_2_1_40_1","volume-title":"Some optimal inapproximability results. J. ACM 48 (July","author":"H\u00e5stad Johan","year":"2001","unstructured":"Johan H\u00e5stad . 2001. Some optimal inapproximability results. J. ACM 48 (July 2001 ), 798--859. Issue 4. Johan H\u00e5stad. 2001. Some optimal inapproximability results. J. ACM 48 (July 2001), 798--859. Issue 4."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766991"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008374125234"},{"key":"e_1_2_1_45_1","unstructured":"Ravi Kannan. 2008. Personal communication. Ravi Kannan. 2008. Personal communication."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of Computer Science and Statistics 12th Annual Symposium on the Interface. 173","author":"Karp R.","year":"1979","unstructured":"R. Karp . 1979 . Probabilistic analysis of graph-theoretic algorithms . In Proceedings of Computer Science and Statistics 12th Annual Symposium on the Interface. 173 . R. Karp. 1979. Probabilistic analysis of graph-theoretic algorithms. In Proceedings of Computer Science and Statistics 12th Annual Symposium on the Interface. 173."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.59"},{"key":"e_1_2_1_50_1","volume-title":"Vecchi","author":"Kirkpatrick Scott","year":"1983","unstructured":"Scott Kirkpatrick , D. Gelatt Jr ., and Mario P . Vecchi . 1983 . Optimization by simmulated annealing. Science 220, 4598 (1983), 671--680. Scott Kirkpatrick, D. Gelatt Jr., and Mario P. Vecchi. 1983. Optimization by simmulated annealing. Science 220, 4598 (1983), 671--680."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1300"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"L. Minder and D. Vilenchik. 2009. Small clique detection and approximate Nash equilibria. 5687 (2009) 673--685. L. Minder and D. Vilenchik. 2009. Small clique detection and approximate Nash equilibria. 5687 (2009) 673--685.","DOI":"10.1007\/978-3-642-03685-9_50"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786440009463897"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Bart Selman Henry Kautz and Bram Cohen. 1995. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 521--532. Bart Selman Henry Kautz and Bram Cohen. 1995. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 521--532.","DOI":"10.1090\/dimacs\/026\/25"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1666"},{"key":"e_1_2_1_60_1","volume-title":"Duchi","author":"Steinhardt Jacob","year":"2015","unstructured":"Jacob Steinhardt and John C . Duchi . 2015 . Minimax rates for memory-bounded sparse linear regression. In COLT. 1564--1587. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v40\/Steinhardt15.html. Jacob Steinhardt and John C. Duchi. 2015. Minimax rates for memory-bounded sparse linear regression. In COLT. 1564--1587. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v40\/Steinhardt15.html."},{"key":"e_1_2_1_61_1","unstructured":"J. Steinhardt G. Valiant and S. Wager. 2016. Memory communication and statistical queries. In COLT. 1490--1516. J. Steinhardt G. Valiant and S. Wager. 2016. Memory communication and statistical queries. In COLT. 1490--1516."},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Bal\u00e1zs Sz\u00f6r\u00e9nyi. 2009. Characterizing statistical query learning: Simplified notions and proofs. In ALT. 186--200. Bal\u00e1zs Sz\u00f6r\u00e9nyi. 2009. Characterizing statistical query learning: Simplified notions and proofs. In ALT. 186--200.","DOI":"10.1007\/978-3-642-04414-4_18"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1987.10478458"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940812"},{"key":"e_1_2_1_67_1","unstructured":"T. Wang Q. Berthet and R. J. Samworth. 2014. Statistical and computational trade-offs in estimation of sparse principal components. ArXiv E-prints (Aug. 2014). T. Wang Q. Berthet and R. J. Samworth. 2014. Statistical and computational trade-offs in estimation of sparse principal components. ArXiv E-prints (Aug. 2014)."},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Ke Yang. 2001. On learning correlated boolean functions using statistical queries. In ALT. 59--76. Ke Yang. 2001. On learning correlated boolean functions using statistical queries. In ALT. 59--76.","DOI":"10.1007\/3-540-45583-3_7"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.003"},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","unstructured":"Andrew Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In FOCS. 222--227. Andrew Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In FOCS. 222--227.","DOI":"10.1109\/SFCS.1977.24"},{"key":"e_1_2_1_71_1","volume-title":"Wainwright","author":"Zhang Yuchen","year":"2013","unstructured":"Yuchen Zhang , John C. Duchi , Michael I. Jordan , and Martin J . Wainwright . 2013 . Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS. 2328--2336. Yuchen Zhang, John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS. 2328--2336."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046674","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3046674","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3046674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:24Z","timestamp":1750218624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,15]]},"references-count":71,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3046674"],"URL":"https:\/\/doi.org\/10.1145\/3046674","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,15]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}