{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:26:55Z","timestamp":1762100815997,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"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.1374484","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"749-758","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Optimal query complexity bounds for finding graphs"],"prefix":"10.1145","author":[{"given":"Sung-Soon","family":"Choi","sequence":"first","affiliation":[{"name":"Yonsei University, Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeong Han","family":"Kim","sequence":"additional","affiliation":[{"name":"Yonsei University, Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.5555\/61992"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1007\/978-3-540-27836-8_12"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1137\/S0895480103431071"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.5555\/645413.652146"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1137\/S0097539702420139"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1007\/978-3-540-27819-1_15"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.5555\/1248547.1248626"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1038\/nrg1272"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/369133.369152"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1007\/11604686_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/234533.234564"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_3_2_1_13_1","volume-title":"Almost tight upper bound for finding Fourier coefficients of k-bounded pseudo-Boolean functions. Submitted to the 21st Annual Conference on Learning Theory (COLT","author":"Choi S. S.","year":"2008","unstructured":"S. S. Choi , K. Jung , and J. H. Kim . Almost tight upper bound for finding Fourier coefficients of k-bounded pseudo-Boolean functions. Submitted to the 21st Annual Conference on Learning Theory (COLT 2008 ), 2008.]] S. S. Choi, K. Jung, and J. H. Kim. Almost tight upper bound for finding Fourier coefficients of k-bounded pseudo-Boolean functions. Submitted to the 21st Annual Conference on Learning Theory (COLT 2008), 2008.]]"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1109\/TEVC.2008.928499"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1109\/TEVC.2007.892764"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1007\/BF00533057"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1007\/BF00531753"},{"key":"e_1_3_2_1_19_1","volume-title":"Springer Verlag","author":"Ewens W.","year":"1979","unstructured":"W. Ewens . Mathematical Population Genetics . Springer Verlag , 1979 .]] W. Ewens. Mathematical Population Genetics. Springer Verlag, 1979.]]"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1093\/genetics\/65.4.707"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1016\/0304-3975(76)90059-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1007\/s10589-009-9261-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.5555\/646717.701901"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.5555\/523986.857987"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.5555\/647907.739974"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1016\/S0166-218X(98)00070-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1007\/s004530010033"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.5555\/1761233.1761361"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1162\/1063656043138914"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1006\/jcss.1997.1533"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1162\/10636560151075112"},{"key":"e_1_3_2_1_32_1","first-page":"527","volume-title":"Lectures in the Sciences of Complexity","author":"Kauffman S. A.","year":"1989","unstructured":"S. A. Kauffman . Adaptation on rugged fitness landscapes . In D. Stein, editor, Lectures in the Sciences of Complexity , pages 527 -- 618 . Addison Wesley , 1989 .]] S. A. Kauffman. Adaptation on rugged fitness landscapes. In D. Stein, editor, Lectures in the Sciences of Complexity, pages 527--618. Addison Wesley, 1989.]]"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1016\/S0022-5193(87)80029-2"},{"key":"e_1_3_2_1_34_1","volume-title":"The Genetic Basis of Evolutionary Change","author":"Lewontin R.","year":"1974","unstructured":"R. Lewontin . The Genetic Basis of Evolutionary Change . Columbia University Press , 1974 .]] R. Lewontin. The Genetic Basis of Evolutionary Change. Columbia University Press, 1974.]]"},{"key":"e_1_3_2_1_35_1","volume-title":"On B2-sequences of vectors. Journal of Number Theory, 4:261--265","author":"Lindstr\u00f6m B.","year":"1972","unstructured":"B. Lindstr\u00f6m . On B2-sequences of vectors. Journal of Number Theory, 4:261--265 , 1972 .]] B. Lindstr\u00f6m. On B2-sequences of vectors. Journal of Number Theory, 4:261--265, 1972.]]"},{"key":"e_1_3_2_1_36_1","first-page":"407","volume-title":"Determining subsets by unramified experiments","author":"Lindstr\u00f6m B.","year":"1975","unstructured":"B. Lindstr\u00f6m . Determining subsets by unramified experiments . In J. N. Srivastava, editor, A Survey of Statistical Designs and Linear Models, pages 407 -- 418 . North Holland , 1975 .]] B. Lindstr\u00f6m. Determining subsets by unramified experiments. In J. N. Srivastava, editor, A Survey of Statistical Designs and Linear Models, pages 407--418. North Holland, 1975.]]"},{"key":"e_1_3_2_1_37_1","first-page":"277","article-title":"On the number of real roots of a random algebraic equation","volume":"12","author":"Littlewood J. E.","year":"1943","unstructured":"J. E. Littlewood and A. C. Offord . On the number of real roots of a random algebraic equation . III. Mat. Sbornik , 12 : 277 -- 285 , 1943 .]] J. E. Littlewood and A. C. Offord. On the number of real roots of a random algebraic equation. III. Mat. Sbornik, 12:277--285, 1943.]]","journal-title":"III. Mat. Sbornik"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1073\/pnas.86.16.6191"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1007\/978-1-4615-2696-4_11"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1162\/evco.1999.7.4.353"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1162\/106365600750078808"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1007\/978-3-540-75225-7_24"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_43_1","DOI":"10.1137\/1106009"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1137\/1106010"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_45_1","DOI":"10.1080\/00029890.1963.11992174"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1007\/978-3-540-24855-2_17"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_47_1","DOI":"10.1006\/geno.1999.6048"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.1002\/(SICI)1521-1878(199805)20:5<433::AID-BIES10>3.0.CO;2-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_49_1","DOI":"10.2307\/2387224"}],"event":{"sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '08","name":"STOC '08: Symposium on Theory of Computing","location":"Victoria British Columbia Canada"},"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.1374484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:50Z","timestamp":1750255070000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":49,"alternative-id":["10.1145\/1374376.1374484","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374484","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"}}]}}