tag:blogger.com,1999:blog-3722233.post4755074676378891782..comments2023-03-23T09:50:46.959-05:00Comments on Computational Complexity: Things a Complexity Theorist Should Do At Least OnceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-66312292331175120472012-10-03T21:10:28.358-05:002012-10-03T21:10:28.358-05:00Actually this is a question I thought about (not a...Actually this is a question I thought about (not as a complexity theorist or TCSer but as a mathematician interested in these areas). I had (decades ago) a list of my own which is quite separate from both Suresh and Lance (but perhaps too banale). I dont remember all of it but here is what I remember.<br /><br />1) Say something interesting about sorting and or searching <br /><br />2) Say something interesting about matching<br /><br />3) Say something interesting about linear programming<br /><br />4) Say something intersting about trees/greedy algorithms/matroids<br /><br />5) Say something interesting about integer programming<br /><br />6) Say something intersting about discrete Fourier transform<br /><br />7) Say something interesting about primality and/or factoring.<br /><br />I has a few more items on the list which I do not remember right now.Gil Kalaihttp://gilkalai.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55009799503636729602012-10-01T22:39:30.657-05:002012-10-01T22:39:30.657-05:00"Things a Complexity Theorist Should Do At Le..."Things a Complexity Theorist Should Do At Least Once..."<br /><br />Win a MacArthur award?<br /><br />Congrats Maria Chudnovsky and Dan Spielman.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75436587071827606832012-09-30T16:39:38.631-05:002012-09-30T16:39:38.631-05:00Attempting to settle P versus NP isn't suffici...Attempting to settle <i>P</i> versus <i>NP</i> isn't sufficient; one should speculate on a world in which both <i>P</i>==<i>NP</i> <b>AND</b> <i>P</i>!=<i>NP</i> are true simultaneously. NP Slaglehttps://www.blogger.com/profile/06322388966706601689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62710741439425299182012-09-27T19:44:17.003-05:002012-09-27T19:44:17.003-05:00Rahul: I agree that structural complexity is an o...Rahul: I agree that structural complexity is an outdated name but it is also clear that Lance's bucket list misses out on aspects of complexity that is unrelated to complexity classes.<br /><br />* Prove an unconditional lower bound on the complexity of an important computational problem.<br /><br />Such a result might not produce a single new separation between complexity classes but might simply allow one to better understand the problem at hand.<br /><br /> Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47687264054970520282012-09-27T19:04:17.518-05:002012-09-27T19:04:17.518-05:00Define a new complexity class that has some reason...<i>Define a new complexity class that has some reason for being.</i><br /><br />Under my definition of "reason for being" there are barely a dozen of those.<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53932115294639099562012-09-27T14:42:52.341-05:002012-09-27T14:42:52.341-05:00" ... concrete complexity, which studies thin..." ... concrete complexity, which studies things like unconditional lower bounds for specific problems in various models of computation."<br /><br />A model of computation naturally defines a complexity class. Getting an unconditional lower/upper bound then amounts to putting a problem out of/into a complexity class. <br /><br />I completely agree with Rahul. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69528929268646431222012-09-27T14:26:53.051-05:002012-09-27T14:26:53.051-05:00In the fourth rule of the game, Suresh states anot...In the fourth rule of the game, Suresh states another caveat: his list doesn't include anything related to quantum algorithms, mostly because he "doesn't know enough about quantum algorithm design to add the right elements". I can't see any comment to his post that responds to this. @Scott (Shtetl-Optimized): can I expect you to be as prompt as Lance? :)Alessandrohttps://cs.uwaterloo.ca/~acosenti/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14677765258415415862012-09-27T13:18:12.749-05:002012-09-27T13:18:12.749-05:00@Rahul: See http://en.wikipedia.org/wiki/Structura...@Rahul: See http://en.wikipedia.org/wiki/Structural_complexity_theory. The key sentence is: "In structural complexity the main focus is on complexity classes, as opposed to the study of how individual problems behave, or the analysis of individual algorithms." So structural complexity studies things like the relationship between complexity classes. This is in contrast to concrete complexity, which studies things like unconditional lower bounds for specific problems in various models of computation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53388696078227271942012-09-27T11:31:30.129-05:002012-09-27T11:31:30.129-05:00What exactly is "structural complexity" ...What exactly is "structural complexity" and how is it different from computational complexity? I think it's time to retire the term.Rahulnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20858715240584761222012-09-27T11:04:57.337-05:002012-09-27T11:04:57.337-05:00You have the qualifier "structural" in y...You have the qualifier "structural" in your post but not your title so your list sounds not quite as general wrt complexity as Suresh's is wrt algorithms. Question for readers: What would you add to the list if you got rid of the qualifier?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3853747330293695262012-09-27T10:42:06.443-05:002012-09-27T10:42:06.443-05:00"Define a new complexity class that has some ..."Define a new complexity class that has some reason for being."<br /><br />Define 'some reason' please. One reason would be to cross it off the Complexity Theorist bucket list. That's <i>some</i> reason.Anonymousnoreply@blogger.com