{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:25:10Z","timestamp":1761611110502,"version":"3.28.0"},"reference-count":42,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181992","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T15:35:00Z","timestamp":1056641700000},"page":"669-678","source":"Crossref","is-referenced-by-count":10,"title":["Power from random strings"],"prefix":"10.1109","author":[{"given":"E.","family":"Allender","sequence":"first","affiliation":[]},{"given":"H.","family":"Buhrman","sequence":"additional","affiliation":[]},{"given":"M.","family":"Koucky","sequence":"additional","affiliation":[]},{"given":"D.","family":"van Melkebeek","sequence":"additional","affiliation":[]},{"given":"D.","family":"Ronneburger","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743524"},{"key":"35","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"17","first-page":"2","article-title":"Search of an easy witness: Exponential time vs. probabilistic polynomial time","author":"impagliazzo","year":"2001","journal-title":"CCC"},{"key":"36","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"34","article-title":"Super-bits, demi-bits, and NP?\/qpoly-natural proofs","author":"rudich","year":"1997","journal-title":"RANDOM Volume 1269 of LNCS"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"39","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90004-X"},{"key":"13","first-page":"468","article-title":"An improved worst-case to average-case connection for lattice problems","author":"cai","year":"1997","journal-title":"FOCS"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"37","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"11","first-page":"158","article-title":"Some recent progress on the complexity of lattice problems","author":"cai","year":"1999","journal-title":"CCC"},{"key":"38","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004348"},{"key":"12","first-page":"308","article-title":"On the average-case hardness of CVP","author":"cai","year":"2001","journal-title":"FOCS"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1763"},{"key":"42","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"},{"key":"41","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90074-P"},{"key":"40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90132-0"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1137\/0220059"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60922-9_3"},{"key":"25","first-page":"19","article-title":"Relativization of questions about log space reducibility","volume":"10","author":"ladner","year":"1976","journal-title":"MST"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80060-1"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1966-0216950-5"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237838"},{"article-title":"PRIMES is in P","year":"2002","author":"agrawal","key":"2"},{"key":"10","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1137\/S0097539799360148","article-title":"Randomness is hard","volume":"30","author":"buhrman","year":"2001","journal-title":"SIAM J Comput"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8191-1"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509995"},{"key":"7","first-page":"63","article-title":"Relationship between density and deterministic complexity of NP-complete languages","author":"berman","year":"1978","journal-title":"ICALP Volume 62 of LNCS"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"article-title":"Digitalized signatures and public-key functions as intractible as factorization","year":"1979","author":"rabin","key":"32"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21916"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45294-X_1"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1484"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"}],"event":{"name":"43rd Annual IEEE Symposium on Foundations of Computer Science","acronym":"SFCS-02","location":"Vancouver, BC, Canada"},"container-title":["The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8411\/26517\/01181992.pdf?arnumber=1181992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T22:46:26Z","timestamp":1497566786000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181992\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":42,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181992","relation":{},"subject":[]}}