tag:blogger.com,1999:blog-3722233.post115712211179912786..comments2024-03-04T02:59:26.350-06:00Comments on Computational Complexity: Favorite Theorems: Unique WitnessesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1157535263051510692006-09-06T04:34:00.000-05:002006-09-06T04:34:00.000-05:00No! Proof of ECCC TR06-062 still has some problem....No! Proof of ECCC TR06-062 still has some problem. <BR/><BR/>I am not sure if an incomplete result deserves much discussion - but the reason for which it was discussed was following:<BR/><BR/>Is ECCC kind of model "good"? Where good-ness was observed from various perspective, namely and most importantly can author timestamp work by ECCC submission and claim that the "proof belongs to him".<BR/><BR/>I rather see the purpose of submitting a paper in ECCC as a way to receive peer-review comments. I am not sure if this is an inverted way of using ECCC (people seem to have opposite view point). For me, neither do I see it embarrassing to get my mistakes reviewed by others nor do I intend to submit so that I can claim that the "proof belongs to me"(hard to prove this claim though :), but following explanation might serve). <BR/><BR/>I do not belong to academia, and I do not find much opportunity to get my works discussed with others or get them reviewed. I did not indented to live with that, and rather decided to post in ECCC – as even one constructive comment will be worth for me, which will allow me to correct my work quickly. It is rather in this desperation the ``problematic paper’’ exists as TR06-062. While I must say I am grateful to, Chris Calabro and Yann Barsamian, who commented on the earlier version, and I am working on them.<BR/><BR/><BR/>One final comment: First comment in this post:<BR/><BR/>Anonymous said... <BR/>ECCC TR06-062 <BR/>9:47 PM, September 02, 2006 <BR/><BR/>Is not posted by me, :) of course I would not want this to be discussed much - before I complete my duty (i.e. correct my work).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1157518577881546592006-09-05T23:56:00.000-05:002006-09-05T23:56:00.000-05:00What's up with ECCC TR06-062?There seem to be much...What's up with ECCC TR06-062?<BR/>There seem to be much of a discussion around this report. Is the proof there valid?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1157433379736185452006-09-05T00:16:00.000-05:002006-09-05T00:16:00.000-05:00Isolation Lemma of [MVV87] was used to prove NL/po...Isolation Lemma of [MVV87] was used to prove NL/poly = UL/poly by <A HREF="http://dx.doi.org/10.1137/S0097539798339041" REL="nofollow">Reinhardt and Allender</A>. To show that NL/poly = UL/poly it is sufficient to show that NL/poly \subseteq UL/poly, other side is implied by definition, for which one can present a UL/poly algorithm for problem STCONN. However, to do this in UL, one have to reduce STCONN to a problem of finding a unique path in the input graph G from s to t. This was done by a reduction used by Wigderson to show NL/poly \subseteq \Oplus L/poly. Reduction works in logspace by assigning random weights (between [1,4.|V|^2.|E|]) to the edges of the graph, while ensuring that there will be a unique minimum weight s-t-path on weighted graph with high probability iff there is one s-t-path in original graph (i.e. a RL reduction), and then turning the weighted graph back to a unweighted graph while preserving the reduction. In fact this weight assignment can ensure that the shortest distance between every pair of nodes is achieved by a unique path with high probability (call it min unique graph). A weight function is then ``good'' if it converts the graph to a min unique graph. A simple counting argument shows that in a collection of polynomially many random weight functions one is ``good'' for every possible input graphs. <BR/><BR/>Also, see some more application of isolation lemma in complexity of Matching (``Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds'',Eric Allender and Klaus Reinhardt and S. Zhou)<BR/><BR/>See Hemaspaandra and Ogihara's book for a chapter on Isolation Lemma.<BR/><BR/>Stasys Jukna's book ``Extremal Combinatorics'' has a section on Isolation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1157251630574580912006-09-02T21:47:00.000-05:002006-09-02T21:47:00.000-05:00ECCC TR06-062ECCC TR06-062Anonymousnoreply@blogger.com