tag:blogger.com,1999:blog-3722233.post8522252994213818704..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: FCRC 2011. Part I of... maybe I, maybe more.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-83767768474845574802011-06-18T12:27:21.657-05:002011-06-18T12:27:21.657-05:00Anon
1) THANKS for telling me the link was broken...Anon<br /><br />1) THANKS for telling me the link was broken. I have fixed it.<br /><br />2) The papers original motivation was as follows: Large Ramsey is NOT provable in PA. Hence, if we formulate its negation in Prop Logic this may lead to a prop fml that requires a long proof in some proof system.<br />They ended up showing (contingent on a resonable assumption) that a<br />VERSION of Large Ramsey, that IS<br />probable in PA (and is in the notes I linked to) requires a long proof.<br /><br />3) What I find odd is that since<br />Ramsey and Large Ramsey seem HARDER than PHP, proving that proofs of them are long should be easier. A direct proof that (say)<br />Ramsey requires a long proof may lead to better bounds.<br /><br />4) My definition of Proof Theory was probably not broad enough.<br />If you have a good alternative definition that encompasses more of it then please comment.<br />(Wikipedia had an entry on it but not real definition of it.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37720874235531036842011-06-18T04:38:46.186-05:002011-06-18T04:38:46.186-05:00Some points about your point 5.
1. the link to t...Some points about your point 5. <br /><br />1. the link to the "writeup of the version of Large Ramsey they were talking about" is broken. <br /><br />2. the following sentence is ill-formed.<br />"This talk tried to use a theorem (the Paris Harrington Ramsey Theory) that is not provable in Peano Arithmetic requires a long proof in some systems."<br /><br />3. "This is rather odd-": are reductions and conditional results so odd? Also, the paper says an upper bound is also proved. The status of the standard Ramsey Theorem in Proof Complexity seems to be similar. <br /><br />4. I have never heard "Proof Complexity" used in connection with your meaning "(1) proving that theorem X NEEDED to use Axioms Y or had to be nonconstructive of level Z", although it might make sense! Usually (1) is referred to generically as Proof Theory, or more specifically as Reverse Mathematics, isn't it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30689158991640851272011-06-17T17:50:43.526-05:002011-06-17T17:50:43.526-05:00Anyone knows if STOC is going to be make the talks...Anyone knows if STOC is going to be make the talks available online like FOCS (http://techtalks.tv/events/13/)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3382681725610288892011-06-16T00:28:35.567-05:002011-06-16T00:28:35.567-05:00GASARCH: Sorry about missing the second best paper...GASARCH: Sorry about missing the second best paper award -- it was unintentional and I added it to my page (the page mentioned in "This seems to be unknown to thiswebsite.").Jeff Huanghttp://jeffhuang.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49672019500272283032011-06-15T09:52:36.212-05:002011-06-15T09:52:36.212-05:00Anon: THANKS, I have ADDED that information to the...Anon: THANKS, I have ADDED that information to the post.<br />(about the shared BEST PAPER award)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1445089354396672812011-06-15T09:32:22.459-05:002011-06-15T09:32:22.459-05:00From page iii of the (electronic) proceedings:
--...From page iii of the (electronic) proceedings:<br /><br />-------------------------------<br />The committee selected two papers for a Best Paper Award: “Electrical Flows, Laplacian Systems, and<br />Faster Approximation of Maximum Flow in Undirected Graphs,” by Paul Christiano, Jonathan A. Kelner,<br />Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng, and “Subexponential Lower Bounds for<br />Randomized Pivoting Rules for the Simplex Algorithm,” by Oliver Friedmann, Thomas Dueholm Hansen,<br />and Uri Zwick. The committee selected “Analyzing Network Coding Gossip Made Easy” by Bernhard<br />Haeupler for the Danny Lewin Best Student Paper Award.<br />-------------------------------<br /><br />PS: I'm not an author of any of these papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47394044746074656062011-06-15T09:16:22.000-05:002011-06-15T09:16:22.000-05:00Ryan: Actually yesterday the link, and part of CMU...Ryan: Actually yesterday the link, and part of CMU, was actually down.<br />However, when it came back the link I had only pointed to a page which listed the paper. I have changed it so that it now links to the link you specified.<br /><br />Anonymous who says there were two STOC best paper awards- I was unable to find any mention of a second paper that also got Best Paper<br />so please email me or post the name of the second paper and I will correct my post. OR post that you were in error.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42393345105159329162011-06-15T02:09:41.514-05:002011-06-15T02:09:41.514-05:00The STOC best paper award was shared by two papers...The STOC best paper award was shared by two papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16959619509046419532011-06-14T22:59:05.389-05:002011-06-14T22:59:05.389-05:00What a nice post, Bill. Thanks!What a nice post, Bill. Thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28399664011181539402011-06-14T19:49:03.526-05:002011-06-14T19:49:03.526-05:00The link to my paper is not down. The link has alw...The link to my paper is not down. The link has always been<br /><br />http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf<br /><br />That link does not appear on my projects page -- sorry about that. I can update the page. <br /><br />I can also put a version on ECCC. I didn't think the paper's absence from ECCC was such an important issue.ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53873849223814977202011-06-14T18:03:15.259-05:002011-06-14T18:03:15.259-05:00Regarding "Non-Uniform ACC Circuit Lower Boun...Regarding "Non-Uniform ACC Circuit Lower Bounds" being unavailable because it is hosted privately, there is this new site called the ECCC (http://eccc.hpi-web.de/) that hosts papers forever!!! And now another new one called the arXiv (http://arxiv.org/)! It truly is a remarkable age; what will people dream up next? (Maybe a cell phone with a camera?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54813986499592199182011-06-14T16:50:39.837-05:002011-06-14T16:50:39.837-05:00"Part I of I" is a title I would actuall..."Part I of I" is a title I would actually understand, I think. It requires some knowledge of Roman numerals, no? Or maybe some ability to distinguish vertical strokes from ones and eyes. So it's nontrivial.<br /><br />Something like "Part II of I" would be somewhat incomprehensible.<br /><br />Although maybe not, as in the slide Bo'az Klartag posted for his STOC talk: "Quantum Junction,<br />Get In Both Lanes".Mickihttps://www.blogger.com/profile/11592612022853202507noreply@blogger.com