tag:blogger.com,1999:blog-3722233.post3963526307631985738..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Report from Barriers II Part 1Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-85563529449787774472010-09-03T01:40:46.536-05:002010-09-03T01:40:46.536-05:00Check Suresh's Geomblog for a summery by Piotr...Check Suresh's Geomblog for a summery by Piotr Indyk.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5465301954149268572010-09-02T12:57:32.706-05:002010-09-02T12:57:32.706-05:00Aaron, if nobody else is going to post about this ...<i>Aaron, if nobody else is going to post about this as a Barriers II theme, maybe you might consider doing it?</i><br /><br />Thank you for the flattering request, but I didn't take enough notes to present the precision I'm sure you want. However... one of the main speakers who dealt with this theme was Jeff Erickson, who blogs very well. Perhaps, if he's reading this, he might oblige?Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90306267325833378112010-09-02T10:13:50.717-05:002010-09-02T10:13:50.717-05:00Aaron Sterling says: A common theme was the genera...Aaron Sterling says: <i>A common theme was the generalization of algorithms in Euclidean space to other geometric spaces, such as doubling spaces, or spaces of higher genus than the plane.</i><br /><br />The overall theme of "geometric generalization" is immensely interesting to engineers ... the results, the proof technologies, and the verification procedures all are of great practical utility.<br /><br />Aaron, if nobody else is going to post about this as a Barriers II theme, maybe you might consider doing it?John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42323022686738977762010-09-01T11:10:11.291-05:002010-09-01T11:10:11.291-05:00To provide an alternative perspective:
I thought ...To provide an alternative perspective:<br /><br />I thought the only full-on surveys were the ones presented by Sanjeev Arora and Paul Beame. The other presentations, while good, felt job-talky (in fact, one presenter said "The next slides are from my job talk," and another presenter said, "My co-author will be on the job market soon. Hire her!") I got a good sense of what the speaker's strengths were as a researcher, and recent results the speaker obtained, but most talks were more a presentation of recent data points (current best-known results from the work of Speaker X) that could later be used to build a larger theory, instead of being attempts to provide an overarching picture of what was really going on.<br /><br />(Since John Sidles brought up the Aaronson/Drucker work, I'll use that as an example: it is unclear to me where their computation model stands with respect to other models of optical computing, e.g., the work of Damien Woods. I couldn't help wondering if there was some independent rediscovery possible here, as I've seen that before within natural computing, with so many different models running around, and people focused overmuch on their own thing. Aaronson may well be familiar with optical computing background, I don't know, but his talk offered up his work without providing a larger context. This focus on one's own work, without weighting it relative to the work of others in the field, was a common pattern.)<br /><br />As a result, I thought the strongest talk was Prasad Raghavendra's -- to the point where I'd say that if you're only going to watch one video, that's the one to watch. Raghavendra not only discussed his own recent results, but presented a (still-unfinished) metatheory of CSPs. It was just beautiful.<br /><br />To compare Barriers I with Barriers II, more of the talks in Barriers I took the form of surveys and analysis of the field. This was, perhaps, because more of the speakers at Barriers I were senior members of the community, while more of the speakers at Barriers II were at or near the postdoc stage. Even so, I thought Barriers II was a better workshop in the following important sense: there was a much clearer sense of progress, and many more approachable open problems. As an example, a common theme was the generalization of algorithms in Euclidean space to other geometric spaces, such as doubling spaces, or spaces of higher genus than the plane. The "barrier question" with such research was to determine whether there *was* a barrier: can the algorithms be generalized if we are just more careful, or is there a fundamental difference between the spaces?Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25013117435602196142010-08-31T14:27:42.271-05:002010-08-31T14:27:42.271-05:00My feeling is that our "barriers" lack c...My feeling is that our "barriers" lack clear mathematical ground, are too vague or too "concept dependent". But what about the following REAL barrier.<br /><br />For a boolean matrix A, let t(A) be the smallest number t for which it is possible to write A as a Hadamard (i.e. entry-wise) product of t boolean matrices, the 0-entries in each of which can be covered by at most t all-0 submatrices.<br /><br />Easy counting shows that nXn matrices A with t(A) at least n^{1/2} exist.<br /><br />Problem: Exhibit an explicit matrix A with t(A) at least n^c for an arbitrary small constant c>0$.<br /><br />This would give the first superlinear lower bound for log-depth circuits, a 30 years old open problem in CC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11459602157169865022010-08-31T12:38:49.076-05:002010-08-31T12:38:49.076-05:00Ahahaha
"another game that is not much fun&q...Ahahaha <br />"another game that is not much fun"<br />I don't know if I totally agree with the concept of this joke, having taught a course in game theory, but the sentence is hilarious!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64766782562854664832010-08-31T12:16:59.932-05:002010-08-31T12:16:59.932-05:00To his credit, Scott Aaronson already has posted h...To his credit, Scott Aaronson already has posted his slides from <i>Barriers II</i>.<br /><br /> I was hoping that either Scott or Bill would weblog about this research ... but no such luck (so far) ... and that's why I've gently lobbied Scott to have his student Alex Arkhipov <a href="http://scottaaronson.com/blog/?p=463#comment-47014" rel="nofollow">do a guest weblog</a>.<br /><br />Perhaps inviting more students to do more guest weblogs might be a good thing all-round? <br /><br />"Better for them, better for us, better for everyone," as Capt. James T. Kirk once said it.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57941366405178797432010-08-31T10:35:50.405-05:002010-08-31T10:35:50.405-05:00They are doing a great service by making the video...They are doing a great service by making the videos of workshops in CCI available on-line. Thanks to the people in CCI, the organizers, and the speakers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9163605095343164932010-08-31T09:27:15.922-05:002010-08-31T09:27:15.922-05:00YES- they said Video's should be up within a m...YES- they said Video's should be up within a month. Someone from<br />Barriers Organizing comm- please<br />confirm, deny, or clarify.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54646626829329965732010-08-31T09:22:14.470-05:002010-08-31T09:22:14.470-05:00This also lead to the following oddity: the day on...<i>This also lead to the following oddity: the day on (say) Quantum had very few quantum people at it (except the speakers) </i><br /><br><br />Well, Barriers II was colliding with <a rel="nofollow">AQIS 2010</a> in Tokyo.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56911989456229666032010-08-31T09:20:37.696-05:002010-08-31T09:20:37.696-05:00@Bill: Thank you.
@Dave: Probably they will post ...@Bill: Thank you.<br /><br />@Dave: Probably they will post the videos sometime (a few months?) after the workshop.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82119951194217186482010-08-31T09:18:00.154-05:002010-08-31T09:18:00.154-05:00Did they post slides or video?Did they post slides or video?Dave Backushttps://www.blogger.com/profile/11472846910681816429noreply@blogger.com