tag:blogger.com,1999:blog-3722233.post115435324991211277..comments2023-03-23T09:50:46.959-05:00Comments on Computational Complexity: Full DerandomizationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-1155128749511964482006-08-09T08:05:00.000-05:002006-08-09T08:05:00.000-05:00Most notably you can derandomize Sipser's construc...Most notably you can derandomize Sipser's <A HREF="http://doi.acm.org/10.1145/800061.808762" REL="nofollow">constructions</A> to show that for any set A a subset of strings of length n, for all x in A, KD^poly(x|A) is at most log |A| + log log |A| + O(1).Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1155100515584754582006-08-09T00:15:00.000-05:002006-08-09T00:15:00.000-05:00What would be the applications for resource-bounde...What would be the applications for resource-bounded Kolmogorov complexity theory? Thanks!thedatabasehttps://www.blogger.com/profile/00973795967472720213noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154582977707856582006-08-03T00:29:00.000-05:002006-08-03T00:29:00.000-05:00One can also derandomize Polynomial Identity Testi...One can also derandomize Polynomial Identity Testing, which is interesting since the work of Kabanets and Impagliazzo. Derandomization of this implies separating NEXP from P/poly. <BR/><BR/>Also it is not just all of statistical zero-knowledge lie in NP?co-NP, but also languages having interactive proof of log(n) statistical knowledge complexity will be in NP?co-NP. Languages having interactive proof in which prover sends bounded number of bits will also be in NP?co-NP?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154526867383621532006-08-02T08:54:00.000-05:002006-08-02T08:54:00.000-05:00ref. on the "ramsey thing":one nice survey by Vera...ref. on the "ramsey thing":<BR/>one nice <A HREF="http://www.combinatorics.org/Surveys/ds13.pdf" REL="nofollow">survey</A> by Vera Rosta<BR/><BR/>Possibly start with these and expand the reference graph :).<BR/><BR/><A HREF="www.math.ias.edu/~avi/PUBLICATIONS/ABSTRACT/biw04.pdf" REL="nofollow">Extracting randomness using few independent sources</A><BR/><BR/><A HREF="http://doi.acm.org/10.1145/1132516.1132611" REL="nofollow">2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction</A><BR/><BR/><A HREF="http://doi.acm.org/10.1145/1060590.1060592" REL="nofollow">Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154458496854782342006-08-01T13:54:00.000-05:002006-08-01T13:54:00.000-05:00Can you please give a reference to the ramsey thin...Can you please give a reference to the ramsey thing you mentionedAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154447747159867892006-08-01T10:55:00.000-05:002006-08-01T10:55:00.000-05:00I like this survey by Peter Bro Miltersen.I like this <A HREF="http://www.daimi.au.dk/~bromille/Papers/dccJun9.ps" REL="nofollow">survey</A> by Peter Bro Miltersen.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154445724483967972006-08-01T10:22:00.000-05:002006-08-01T10:22:00.000-05:00Where can I find a proof that that assumption inde...Where can I find a proof that that assumption indeed implies BPP = P? It is probably a classical paper (or set of papers) but I am not that familiar with complexity theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154433011141735182006-08-01T06:50:00.000-05:002006-08-01T06:50:00.000-05:00By "short" I mean a polynomial (in the size of the...By "short" I mean a polynomial (in the size of the graph) long list and by "most" I mean at least one will be Ramsey. A more careful analysis and/or allowing slightly larger independent sets and cliques and "most" would really mean "nearly all".Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154380957447413982006-07-31T16:22:00.000-05:002006-07-31T16:22:00.000-05:00Can you please give more details on the short list...Can you please give more details on the short list of mostly ramsey graphs. What is "short list" and what is "most"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154356193535131782006-07-31T09:29:00.000-05:002006-07-31T09:29:00.000-05:00keep hoping!keep hoping!Anonymousnoreply@blogger.com