tag:blogger.com,1999:blog-3722233.post117401054360395527..comments2021-03-01T13:59:11.893-06:00Comments on Computational Complexity: A Place for Open ProblemsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-3722233.post-1175888866867165762007-04-06T14:47:00.000-05:002007-04-06T14:47:00.000-05:00Sorry for my sloppyness, here is the linkable url ...Sorry for my sloppyness, here is the linkable url for our new page:<BR/><BR/><A HREF="http://dm.irmacs.sfu.ca" REL="nofollow">Openmap</A><BR/><BR/>Matt DeVosAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175888684184190042007-04-06T14:44:00.000-05:002007-04-06T14:44:00.000-05:00As it happens, Robert Samal and myself (Matt DeVos...As it happens, Robert Samal and myself (Matt DeVos) have just created a wiki for open problems. It is more or less in a beta form at the moment, but we think this is an idea whose time has come. We haven't settled on a name yet, but the url is as follows:<BR/><BR/>http://dm.irmacs.sfu.ca<BR/><BR/>We are keen for contributions and suggestions. <BR/><BR/>Matt DeVosAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174279697656068722007-03-19T00:48:00.000-05:002007-03-19T00:48:00.000-05:00Why not add the feature to complexity zoo itself?M...<I>Why not add the feature to complexity zoo itself?</I><BR/><BR/>My complexity zoology expert system, which is linked from complexity zoo, recognizes the difference between incomplete data (which is marked gray in the Javascript diagram) and open problems (which are marked green). Open cases may be the weakest side of the current dataset, and I would certainly welcome more feedback.<BR/><BR/>But there is a serious problem with the Complexity Zoo site and even more, Complexity Zoology. Namely, TCS has largely move beyond relations among complexity classes and onto other problems. Except for the quantum classes, both projects are largely a review of the 1960s through the 1990s. It is hard to get the attention of the experts today, although they still respect these old results.Greg Kuperberghttps://www.blogger.com/profile/03777237240198671451noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174176662479467692007-03-17T20:11:00.000-05:002007-03-17T20:11:00.000-05:00Why not add the feature to complexity zoo itself? ...Why not add the feature to complexity zoo itself? It would not be too much of a hassle, and it would be more appropriate.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174159103919472452007-03-17T15:18:00.000-05:002007-03-17T15:18:00.000-05:00any bets on who will win the acm doctoral disserta...any bets on who will win the acm doctoral dissertation award this year?<BR/>or at least any takes on the strongest theory thesis eligible for the award?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174133113127229782007-03-17T08:05:00.000-05:002007-03-17T08:05:00.000-05:00The 20th Century view is that a list of open probl...The 20th Century view is that a list of open problems provides a view of the underlying & fundamental unity of mathematics (in the tradition of David Hilbert).<BR/><BR/>A 21st Century view might be, that the list of fundamental mathematical theorems is exponentially long, and therefore, open problem lists are necessarily a very sparse sampling of a set possessing unbounded structural complexity. <BR/><BR/>Any such list is necessarily designed to meet human needs equally as much it is inspired by a search for eternal truth.<BR/><BR/>In other words, don't open problem lists (both past and present) reflect mathematical truth and human nature in roughly equal measure?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174112501849710042007-03-17T02:22:00.000-05:002007-03-17T02:22:00.000-05:00I regularly post open problems on my blog. Here ar...I regularly post open problems on my blog. Here are <A HREF="http://absolutely-regular.blogspot.com/2007/03/geometry-question.html" REL="nofollow">two</A> recent <A HREF="http://absolutely-regular.blogspot.com/2007/03/as-before-define-to-be-set-of-all.html" REL="nofollow">examples</A>; the former has generated quite a bit of good discussion. Occasionally I give open problems as <A HREF="http://absolutely-regular.blogspot.com/2006/12/flac-project-suggestions.html" REL="nofollow">projects</A> for my students...Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174095685039141262007-03-16T21:41:00.000-05:002007-03-16T21:41:00.000-05:00Wet foams vs dry foams. Surface tension keeps the ...Wet foams vs dry foams. Surface tension keeps the surface area small.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174093179104019322007-03-16T20:59:00.000-05:002007-03-16T20:59:00.000-05:00Ryan wrote: or -- it's related to finding the bes...Ryan wrote:<BR/><BR/><I> or -- it's related to finding the best rate for parallel repetition of a simple family of 2P1R games </I><BR/><BR/>but what about <B>foams</B>, man? what's it got to do with the <B>foams</B>??? I just can't wait till CCC!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174091800839571462007-03-16T20:36:00.000-05:002007-03-16T20:36:00.000-05:00Years ago (my god - 94?) I coauthored a survey pap...Years ago (my god - 94?) I coauthored a survey paper with Adleman on open problems in number theoretic complexity. Surprisingly little progress has been made on those...no doubt due to the fact that few people work in the subfield any more. One of the biggies - primes in P was solved.<BR/><BR/>Incidentally I have a bet with Ron Fagin on how P=NP will be resolved. I got 5 to 1 odds!Alvin Anonyhttps://www.blogger.com/profile/15268049341572923471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174084947119520872007-03-16T18:42:00.000-05:002007-03-16T18:42:00.000-05:00It's probably the same post as the previous refere...It's probably the same post as the previous reference, but there is a classical lower bound of Omega(n log n) for element distinctness in any comparison based algorithms. If the algorithm is not comparison based, there are various tricks one could make, from the counting/radix sort (if the numbers not to large) to all kind of other options that would actually sort the numbers, let alone find duplicates.Zaumkahttps://www.blogger.com/profile/12342474039039410266noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174084153054012092007-03-16T18:29:00.000-05:002007-03-16T18:29:00.000-05:00Instead of prizes, it would be nice to have a pred...Instead of prizes, it would be nice to have a prediction market on whether the problems will be solved by a certain date. This would work as a prize for the person who solves the problem, except it's more fair, in the sense that people who prove a big (but not final) step of the proof can also benefit from the prize money.<BR/><BR/>Too bad anti-gambling law don't allow something like this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174083726442561272007-03-16T18:22:00.000-05:002007-03-16T18:22:00.000-05:00To anon poster 11:You may be interested in looking...To anon poster 11:<BR/>You may be interested in looking at Theorem 5 (in page 655) of Ed Reingold's paper, On the optimality of Set Algorithms, JACM 1971. (This paper is free to down from ACM website)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174081947437624312007-03-16T17:52:00.000-05:002007-03-16T17:52:00.000-05:00What kind of items?What kind of items?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174078054057789582007-03-16T16:47:00.000-05:002007-03-16T16:47:00.000-05:00Anon 12: I am looking for an algorithm that is gua...Anon 12: I am looking for an algorithm that is guaranteed to be correct, with worst-case linear running time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174076431353275372007-03-16T16:20:00.000-05:002007-03-16T16:20:00.000-05:00Anon 11:Use a hash table.Anon 11:<BR/><BR/>Use a hash table.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174078873698996492007-03-16T16:01:00.000-05:002007-03-16T16:01:00.000-05:00Why not just add the feature to complexity zoo? It...Why not just add the feature to complexity zoo? It might actually be better to do it this way.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174070741704162852007-03-16T14:45:00.000-05:002007-03-16T14:45:00.000-05:00Here's a problem that's open for me (though I am s...Here's a problem that's open for me (though I am sure the answer is known): given an unsorted list of n items x_1, ..., x_n, is it possible to determine in linear time whether there are distinct indices i, j with x_i = x_j (and, if so, also find i and j)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174062369830204622007-03-16T12:26:00.000-05:002007-03-16T12:26:00.000-05:00Here's one that I've found very vexing: Let A(d) ...Here's one that I've found very vexing: Let A(d) denote the least surface area of a cell that tiles R^d via the translations in Z^d. Improve on the following bounds:<BR/><BR/>sqrt(pi e / 2) sqrt(d) <= A(d)/2 <= d - exp(-Omega(d log d)).<BR/><BR/>(It's a little more natural to consider A(d)/2 than A(d).) <BR/><BR/>The lower bound is by considering a volume-1 sphere, the upper bound by monkeying around a little with a cube's corner. <BR/><BR/>Any proof of A(d)/2 >= 10sqrt(d) or A(d)/2 <= d/10 would be very interesting.<BR/><BR/>For motivation: Either pretend I posted on Suresh's blog (so it's just a problem in geometry); or -- it's related to finding the best rate for parallel repetition of a simple family of 2P1R games.Ryan O'Donnellhttps://www.blogger.com/profile/17737696490831554328noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174062194593421962007-03-16T12:23:00.000-05:002007-03-16T12:23:00.000-05:00I read survey papers, but they take time for autho...I read survey papers, but they take time for authors to write up and can fall out of date quickly. They also reflect the opinion and taste of only a couple authors. I completely agree with Paul Beame about the value of open problems, and I'm sure I would benefit from such a site even with a very knowledgable supervisor. Such a site wouldn't immediately need all of the features Lance mentioned; it might be enough to start with a simple Wiki.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174043469264003462007-03-16T07:11:00.000-05:002007-03-16T07:11:00.000-05:00What's wrong with writing a good survey paper ever...What's wrong with writing a good survey paper every now and then ? <BR/><BR/>Does everything really needs to be Web 2.0 with tags and RSS feeds ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174039113185774192007-03-16T05:58:00.000-05:002007-03-16T05:58:00.000-05:00Why doesn't Scott Aaronson volunteer to do the job...<I>Why doesn't Scott Aaronson volunteer to do the job? :-)</I><BR/><BR/>Sure! Just give me 20 years or so.Scotthttps://www.blogger.com/profile/12161309448306097395noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174037255963592922007-03-16T05:27:00.000-05:002007-03-16T05:27:00.000-05:00While we're at it, how about some place to keep re...While we're at it, how about some place to keep results that do not fit in the taxonomy of the zoo? I'm imagining a wikipedia-clone that is not geared towards being an encyclopedia.<BR/><BR/>Chasing references back and forth through Google feels so 1998.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174031941644420552007-03-16T03:59:00.000-05:002007-03-16T03:59:00.000-05:00Open problems lists can be of considerable benefit...Open problems lists can be of considerable benefit to a community. For example in computational geometry Joe O'Rourke began the <A HREF="http://maven.smith.edu/~orourke/TOPP/" REL="nofollow"> Open Problems Project </A>. (Joe is now joined by Erik Demaine and Joe Mitchell in maintaining the list.) Moreover, open problems are <A HREF="http://geomblog.blogspot.com/2005/05/its-open-problems-time.html" REL="nofollow">annually solicited for SOCG</A>. It helps the community that problems from the list are regularly knocked off. <BR/><BR/>There is no really good reason that we don't have similar lists for many areas in computational complexity. Unfortunately the CCC rump session serves multiple purposes (both announcements of results and of open problems) and is both too short and too broad to be effective for providing this for the field. <BR/><BR/>Smaller, more focused workshops can do this quite well. I have found motivation for some of my own work in open problem lists compiled at workshops on proof complexity and Boolean function complexity. Are there good lists for APPROX or RANDOM? They are sufficiently focused that they would be ideal for producing lists of open problems in their respective areas. <BR/><BR/>Anyone who doubts the value of open problems lists need only look to a certain 107-year old list of 23 problems...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1174024917117555172007-03-16T02:01:00.000-05:002007-03-16T02:01:00.000-05:00Possibly people can post these problems along with...Possibly people can post these problems along with prize money(might be token or lot more than that) like Erdos used to do with his open problems. The prize money (and who it is offered by) would be a reflection of the importance of the problem. Possibly other people can add to the prize to make the problem lucrative and claim that the problem is quite important.Anonymousnoreply@blogger.com