{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:28:41Z","timestamp":1770902921531,"version":"3.50.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032171559","type":"print"},{"value":"9783032171566","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17156-6_20","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:36:18Z","timestamp":1770899778000},"page":"264-277","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact Recovery of\u00a0Planted Cliques in\u00a0Semi-random Graphs"],"prefix":"10.1007","author":[{"given":"Yash","family":"Khanna","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"20_CR1","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 594\u2013598. Society for Industrial and Applied Mathematics, USA (1998)"},{"key":"20_CR2","doi-asserted-by":"publisher","unstructured":"Arora, S., Barak, B., Brunnermeier, M., Ge, R.: Computational complexity and information asymmetry in financial products. Commun. ACM 54(5), 101\u2013107 (2011). https:\/\/doi.org\/10.1145\/1941487.1941511","DOI":"10.1145\/1941487.1941511"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P., Braverman, M., Chlamtac, E.: Inapproximability of np-complete variants of nash equilibrium (2011). https:\/\/arxiv.org\/abs\/1104.3760","DOI":"10.1007\/978-3-642-22935-0_2"},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Barak, B., Hopkins, S., Kelner, J., Kothari, P.K., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM J. Comput. 48(2), 687\u2013735 (2019). https:\/\/doi.org\/10.1137\/17M1138236","DOI":"10.1137\/17M1138236"},{"key":"20_CR5","doi-asserted-by":"publisher","unstructured":"Berthet, Q., Rigollet, P.: Optimal detection of sparse principal components in high dimension. Ann. Stat. 41(4), 1780\u20131815 (2013). https:\/\/doi.org\/10.1214\/13-AOS1127","DOI":"10.1214\/13-AOS1127"},{"key":"20_CR6","doi-asserted-by":"publisher","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an o(n$$\\frac{1}{4}$$) approximation for densest k-subgraph. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 201\u2013210. ACM, New York, NY, USA (2010). https:\/\/doi.org\/10.1145\/1806689.1806719","DOI":"10.1145\/1806689.1806719"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Jha, A.V., Kapralov, M., Manoj, N.S., Mazzali, D., Wrzos-Kaminska, W.: On the robustness of spectral algorithms for semirandom stochastic block models (2024). https:\/\/arxiv.org\/abs\/2412.14315","DOI":"10.52202\/079017-3582"},{"key":"20_CR8","doi-asserted-by":"publisher","unstructured":"Blasiok, J., Buhai, R.D., Kothari, P.K., Steurer, D.: Semirandom planted clique and the restricted isometry property . In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 959\u2013969. IEEE Computer Society, Los Alamitos, CA, USA, October 2024. https:\/\/doi.org\/10.1109\/FOCS61266.2024.00064","DOI":"10.1109\/FOCS61266.2024.00064"},{"key":"20_CR9","doi-asserted-by":"publisher","unstructured":"Blum, A., Spencer, J.: Coloring random and semi-random k-colorable graphs. J. Algorithms 19(2), 204\u2013234 (1995). https:\/\/doi.org\/10.1006\/jagm.1995.1034","DOI":"10.1006\/jagm.1995.1034"},{"key":"20_CR10","doi-asserted-by":"publisher","unstructured":"Boppana, R., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol. 447, pp. 13\u201325. Springer, Heidelberg (1990). https:\/\/doi.org\/10.1007\/3-540-52846-6_74","DOI":"10.1007\/3-540-52846-6_74"},{"key":"20_CR11","doi-asserted-by":"publisher","unstructured":"Buhai, R.D., Kothari, P.K., Steurer, D.: Algorithms approaching the threshold for semi-random planted clique. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 1918\u20131926. ACM, New York, NY, USA (2023). https:\/\/doi.org\/10.1145\/3564246.3585184","DOI":"10.1145\/3564246.3585184"},{"key":"20_CR12","doi-asserted-by":"publisher","unstructured":"Charikar, M., Steinhardt, J., Valiant, G.: Learning from untrusted data. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 47\u201360. ACM, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3055399.3055491","DOI":"10.1145\/3055399.3055491"},{"key":"20_CR13","doi-asserted-by":"publisher","unstructured":"Coja-Oghlan, A.: Solving np-hard semirandom graph problems in polynomial expected time. J. Algorithms 62(1), 19\u201346 (2007). https:\/\/doi.org\/10.1016\/j.jalgor.2004.07.003","DOI":"10.1016\/j.jalgor.2004.07.003"},{"key":"20_CR14","doi-asserted-by":"publisher","unstructured":"Deshpande, Y., Montanari, A.: Finding hidden cliques of size p N\/e n\/e in nearly linear time. Found. Comput. Math. 15(4), 1069\u20131128 (2015). https:\/\/doi.org\/10.1007\/s10208-014-9215-y","DOI":"10.1007\/s10208-014-9215-y"},{"key":"20_CR15","doi-asserted-by":"publisher","unstructured":"Feige, U., Kilian, J.: Heuristics for semirandom graph problems. J. Comput. Syst. Sci. 63(4), 639\u2013671 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1773","DOI":"10.1006\/jcss.2001.1773"},{"key":"20_CR16","doi-asserted-by":"publisher","unstructured":"Feige, U., Krauthgamer, R.: Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms 16, 195\u2013208 (2000). https:\/\/doi.org\/10.1002\/(SICI)1098-2418(200003)16:23.3.CO;2-1","DOI":"10.1002\/(SICI)1098-2418(200003)16:23.3.CO;2-1"},{"key":"20_CR17","doi-asserted-by":"publisher","unstructured":"Grimmett, G.R., McDiarmid, C.J.H.: On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77(2), 313\u2013324 (1975). https:\/\/doi.org\/10.1017\/S0305004100051124","DOI":"10.1017\/S0305004100051124"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Guruswami, V.,Wang, H.P.: Semirandom planted clique via 1-norm isometry property. In: Megow, N., Basu, A. (eds.) Integer Programming and Combinatorial Optimization, pp. 270\u2013282. Springer Nature Switzerland, Cham (2025)","DOI":"10.1007\/978-3-031-93112-3_20"},{"key":"20_CR19","doi-asserted-by":"publisher","unstructured":"Hastad, J.: Clique is hard to approximate within n\/sup 1-\/spl epsiv\/\/. In: Proceedings of 37th Conference on Foundations of Computer Science, pp. 627\u2013636 (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548522","DOI":"10.1109\/SFCS.1996.548522"},{"key":"20_CR20","unstructured":"Juels, A., Peinado, M.: Hiding cliques for cryptographic security. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 678\u2013684. Society for Industrial and Applied Mathematics, USA (1998)"},{"key":"20_CR21","doi-asserted-by":"publisher","unstructured":"Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Cryptography 20(3), 269\u2013280 (2000). https:\/\/doi.org\/10.1023\/A:1008374125234","DOI":"10.1023\/A:1008374125234"},{"key":"20_CR22","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85\u2013103. The IBM Research Symposia Series, Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"20_CR23","unstructured":"Khanna, Y.: Exact recovery of planted cliques in semi-random graphs. CoRR abs\/2011.08447, https:\/\/arxiv.org\/abs\/2011.08447 (2020)"},{"key":"20_CR24","unstructured":"Khanna, Y., Louis, A.: Planted models for the densest $$k$$-subgraph problem. CoRR abs\/2004.13978, https:\/\/arxiv.org\/abs\/2004.13978 (2020)"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-030-83508-8_38","volume-title":"Algorithms and Data Structures","author":"Y Khanna","year":"2021","unstructured":"Khanna, Y., Louis, A., Paul, R.: Independent sets in semi-random hypergraphs. In: Lubiw, A., Salavatipour, M., He, M. (eds.) Algorithms and Data Structures, pp. 528\u2013542. Springer International Publishing, Cham (2021)"},{"key":"20_CR26","doi-asserted-by":"publisher","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for MaxClique, chromatic number and Min-3Lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 226\u2013237. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11786986_21","DOI":"10.1007\/11786986_21"},{"key":"20_CR27","unstructured":"Koiran, P., Zouzias, A.: On the certification of the restricted isometry property. ArXiv abs\/1103.4984, https:\/\/api.semanticscholar.org\/CorpusID:16886247 (2011)"},{"key":"20_CR28","doi-asserted-by":"publisher","unstructured":"Kolla, A., Makarychev, K., Makarychev, Y.: How to play unique games against a semi-random adversary: Study of semi-random models of unique games. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 443\u2013452 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.78","DOI":"10.1109\/FOCS.2011.78"},{"key":"20_CR29","doi-asserted-by":"publisher","unstructured":"Ku\u010dera, L.: Expected complexity of graph partitioning problems. Discrete Appl. Math. 57(2), 193\u2013212 (1995). https:\/\/doi.org\/10.1016\/0166-218X(94)00103-K, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0166218X9400103K, combinatorial optimization 1992","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"20_CR30","doi-asserted-by":"publisher","unstructured":"Louis, A., Venkat, R.: Semi-random graphs with planted sparse vertex cuts: algorithms for exact and approximate recovery. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0107, pp. 101:1\u2013101:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.101","DOI":"10.4230\/LIPIcs.ICALP.2018.101"},{"key":"20_CR31","doi-asserted-by":"publisher","unstructured":"Louis, A., Venkat, R.: Planted models for k-way edge and vertex expansion. In: Chattopadhyay, A., Gastin, P. (eds.) 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0150, pp. 23:1\u201323:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2019.23","DOI":"10.4230\/LIPIcs.FSTTCS.2019.23"},{"key":"20_CR32","doi-asserted-by":"publisher","unstructured":"Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Constant factor approximation for balanced cut in the pie model. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 41\u201349. ACM, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2591796.2591841","DOI":"10.1145\/2591796.2591841"},{"key":"20_CR33","unstructured":"Matula, D.: The largest clique in a random graph. Technical Report, Department of Computer Science, Southern Methodist University (1976). https:\/\/s2.smu.edu\/matula\/Tech-Report76.pdf"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"McKenzie, T., Mehta, H., Trevisan, L.: A new algorithm for the robust semi-random independent set problem. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pp. 738\u2013746. Society for Industrial and Applied Mathematics, USA (2020)","DOI":"10.1137\/1.9781611975994.45"},{"key":"20_CR35","doi-asserted-by":"publisher","unstructured":"Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824\u2013827 (2002). https:\/\/doi.org\/10.1126\/science.298.5594.824","DOI":"10.1126\/science.298.5594.824"},{"key":"20_CR36","doi-asserted-by":"publisher","unstructured":"Mossel, E., Neeman, J., Sly, A.: Consistency thresholds for the planted bisection model. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, pp. 69\u201375. ACM, New York, NY, USA (2015). https:\/\/doi.org\/10.1145\/2746539.2746603","DOI":"10.1145\/2746539.2746603"},{"key":"20_CR37","unstructured":"Steinhardt, J.: Does robustness imply tractability? A lower bound for planted clique in the semi-random model. Electron. Colloquium Comput. Complex. 24, 69 (2017). https:\/\/eccc.weizmann.ac.il\/report\/2017\/069"},{"key":"20_CR38","doi-asserted-by":"publisher","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 681\u2013690. ACM, New York, NY, USA (2006). https:\/\/doi.org\/10.1145\/1132516.1132612","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17156-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:36:24Z","timestamp":1770899784000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17156-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032171559","9783032171566"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17156-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dharwad","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/caldam2026.iitdh.ac.in\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}