tag:blogger.com,1999:blog-3722233.post2206551097570878802..comments2021-05-16T09:01:42.816-05:00Comments on Computational Complexity: Favorite Theorems: Connecting in Log SpaceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-11451660088463751152014-02-10T07:32:21.390-06:002014-02-10T07:32:21.390-06:00@Anonymous 4:15, there is a paper by Martin Hofman...@Anonymous 4:15, there is a paper by Martin Hofmann and Ulrich Schoepp in LICS 2009 giving a negative answer in a certain way:<br />http://www2.tcs.ifi.lmu.de/~schoepp/Docs/reach_conf.pdfJan Johannsenhttps://www.blogger.com/profile/16124485013953473170noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63949836120847780732014-02-07T10:16:01.462-06:002014-02-07T10:16:01.462-06:00The statement of the theorem itself wasn't sur...The statement of the theorem itself wasn't surprising since we generally believe that good derandomization is possible and it was already known that connectivity is in randomized log space. It's not surprising that the result is provable, but it was surprising that Reingold could prove it using current technology.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6235797071440215142014-02-06T16:15:21.250-06:002014-02-06T16:15:21.250-06:00> Intuitively, this result says you can tell if...> Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze.<br /><br />Does it work if we are not allowed to do arithmetic on the index of the locations? Does it work with literally a constant number of locations instead of 'the equivalent of a constant number of locations'?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87478659456967430292014-02-06T15:30:46.235-06:002014-02-06T15:30:46.235-06:00But has anybody succeed to prove that CONN require...But has anybody succeed to prove that CONN requires about n^3 gates in a monotone circuit with fanin-2 AND and OR gates? By Floyd-Warshall dynamic programming algorithm, so many gates are enough. <br /><br />And what about STCONN? Do we need also here about n^3 gates? <br /><br />Space is ok. But why nobody is interested in *time*?stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15547586983318896062014-02-06T12:28:34.963-06:002014-02-06T12:28:34.963-06:00I DETECT based on subtle CLUES that "CAAR REU...I DETECT based on subtle CLUES that "CAAR REU" might be GASARCH in DISGUISE. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74408898333306193962014-02-06T10:12:07.972-06:002014-02-06T10:12:07.972-06:00At the time it was proven was it surprising that i...At the time it was proven was it surprising that it was TRUE or surprising that it was PROVABLE or was it not that surprising (STILL a great result of course).Anonymoushttps://www.blogger.com/profile/00496057724536630931noreply@blogger.com