tag:blogger.com,1999:blog-4975263359731311867.post7858362460171741109..comments2010-12-15T15:01:29.233-05:00Comments on 15-855: Intensive Intro to Computational Complexity: Kolmogorov Complexity and derandomizationRyan O'Donnellhttp://www.blogger.com/profile/01760886084136827344noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-4975263359731311867.post-39543268678645809722009-05-01T03:18:00.000-04:002009-05-01T03:18:00.000-04:00Al05: E. Allender et al. Power from Random Strings...Al05: E. Allender et al. Power from Random Strings<br /><br />BFNW93: L. Babai et al. BPP has subexponential time simulations<br />unless EXPTIME has publishable proofs.<br /><br />BM97: H. Buhrman and E. Mayordomo. An excursion to the Kolmogorov random strings.<br /><br />KC00: V. Kabanets and J.-Y. Cai. Circuit minimization problem.<br /><br />Ko91: K.-I Ko. On the complexity of learning minimum time-bounded turing machines.<br /><br />NW94: N. Nisan and A. Wigderson. Hardness vs randomness.Dafnahttps://www.blogger.com/profile/15699152399095970845noreply@blogger.com