tag:blogger.com,1999:blog-3722233.post6362020260903752053..comments2021-09-21T04:14:03.225-05:00Comments on Computational Complexity: Musing from the Barriers WorkshopLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-75056485809222060742009-09-02T17:36:31.463-05:002009-09-02T17:36:31.463-05:00Will scribe notes or videos from the workshop be m...<i>Will scribe notes or videos from the workshop be made publicly available?</i><br /><br />Yes. In the meantime, though, there is already video up of talks Mulmuley gave at IAS in Feb 09. The first video on that page is similar in content to Mulmuley's talk at Barriers, though I found the Barriers talk more accessible.<br /><br />Video page link here:<br />http://video.ias.edu/csdm/pvsnp<br /><br />I'd like to disagree (slightly) with Rahul S.'s superb post: my favorite two talks were the ones by Mulmuley and by Russell Impagliazzo, because they seemed to be the only two researchers presenting <b>plans</b> to attack P/NP. Impagliazzo exposited "An Axiomatic Approach to Algebrization," and, in particular, pointed to the proof that MIP=NEXP -- and moreover to local checkability as a general proof technique -- as something we already know how to do that neither relativizes nor algebrizes. (This "contradicts" the Aaronson/Wigderson algebrization paper; there's more discussion of this on Shtetl Optimized.) So we haven't shown that all our techniques are dead ends, after all. Impagliazzo argued for a research program to obtain further nonrelativizing results, using, e.g., local checkability, and then to study the behavior of complexity classes under "earth-like oracles" -- oracles under which everything we know to be unconditionally true actually holds.<br /><br />Like Rahul, I'd also like to thank the organizers, volunteers and staff. The event ran smoothly, and I certainly learned a lot.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64862478579232195002009-09-02T16:26:57.685-05:002009-09-02T16:26:57.685-05:00Will scribe notes or videos from the workshop be m...Will scribe notes or videos from the workshop be made publicly available?arnabnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7691087264074107592009-09-02T15:08:13.469-05:002009-09-02T15:08:13.469-05:00Anonymous says: I really don't see much use of...Anonymous says: <i>I really don't see much use of any existing ideas in CS that can hope to contribute in [the GCT] effort.</i><br /><br />The converse is definitely <i>not</i> true ... the geometric framework of representation theory provides a natural framework for its engineering cousin, model order reduction theory, and more broadly, simulation theory.<br /><br />I used to think that these fundamental algebraic/geometric insights were relevant mainly to quantum simulation, however this summer I learned at the FOMMS Conference that the biologists use quite a lot of symplectic geometry even at the classical level---that was algebraic geometry and information theory "busting out" at pretty much every conference I went too.<br /><br />The reason for this emerging unity is that everyone wants all the "Goodness" they can get -- the classical Goodness of thermodynamics; the quantum Goodness of smallest size, fastest speed, and maximal energy efficiency; the informatic Goodness of maximal channel capacity, and the algorithmic Goodness of theories and simulations that (nowadays) bind together both the technologies and communities.<br /><br />Mulmuley's GCT program points to a world in which CS/CT is a broader subject than we thought it was --- and doesn't this same principle apply across the broad, to all branches of science and engineering?<br /><br />On the other hand, pure mathematics <i>is</i> what we thought it was ... the logical foundation for all these many enterprises ... <br /><br />And that's why nowadays even engineers and medical researchers are reading "Yellow Books" ... <br /><br />Greatest ... Mathematical .... Summer ... Ever! :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20783566646633741172009-09-02T14:40:06.189-05:002009-09-02T14:40:06.189-05:00I fully agree that the Landsberg et al. write-up i...I fully agree that the Landsberg et al. write-up is in much more comprehensible<br />and than the original GCT papers -- mainly because it is written in a more standard style. The original GCT papers are burdened with excessive explanations at points (of standard concepts and definitions) which made the reading very uneven.<br /><br />The quibble about who is and isn't a computer scientist is ridiculous. The fact of the matter is that the GCT approach relies very little on the previous developments in TCS, and hopes to achieve its goals through breakthroughs in representation theory. Thus, it is really very much a mathematical project and I really don't see much use of any existing ideas in CS that can hope to contribute in this effort.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62326151079148449102009-09-02T01:15:09.840-05:002009-09-02T01:15:09.840-05:00...result of mathematicians...
Peter Burgisser i...<i> ...result of mathematicians...</i> <br /><br />Peter Burgisser is a computer scientist.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65738734562551473872009-09-01T22:04:38.389-05:002009-09-01T22:04:38.389-05:00I do not agree that the best place for learning ab...I do not agree that the best place for learning about Mulmuley & Sohoni's approach to GCT is in any of their papers on the subject. There is a very nice preprint available at http://www.math.tamu.edu/~jml/BLMW0716.pdf that is basically the result of mathematicians trying to sort out the program from a mathematical perspective. AFAIK, it is the first serious attempt made by experts in geometry and representation theory at understanding the program.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36537719447021117262009-09-01T21:47:50.685-05:002009-09-01T21:47:50.685-05:00It is Kalai, Samorodnitsky and Teng I think.It is Kalai, Samorodnitsky and Teng I think.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72567920058185792802009-09-01T16:19:51.526-05:002009-09-01T16:19:51.526-05:00Not sure what you meant by your third point.
Math...Not sure what you meant by your third point.<br /><br /><em>Mathematicians don't care about constructivity - they believe that proofs exist...It was a question of when Fermat's last theorem would be proved, not whether.</em><br /><br />I don't think that's true. Certainly mathematicians (before Wiles' proof) didn't think Fermat's theorem was necessarily true any more or less strongly than we are convinced that P \neq NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42448480768551730422009-09-01T14:16:15.350-05:002009-09-01T14:16:15.350-05:00I'm obviously not a complexity theorist; all m...I'm obviously not a complexity theorist; all my lower bounds are failed attempts at algorithms.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42589681783829912292009-09-01T12:22:40.220-05:002009-09-01T12:22:40.220-05:00What's a complexity theorist's definition ...<i>What's a complexity theorist's definition of an algorithm? A failed attempt to prove a lower bound. </i><br /><br />Thank you very much for this excellent post, and especially for this amusing aphorism ... the aphorism in itself would have made the meeting well worth attending!John Sidleshttp://www.mrfm.orgnoreply@blogger.com