tag:blogger.com,1999:blog-3722233.post9166117362231983352..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Why do I find this result interesting- MOD 17 SATLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-52605546468404123622007-10-19T15:43:00.000-05:002007-10-19T15:43:00.000-05:00They have finally posted the official FOCS 2007 tr...They have finally posted the official FOCS 2007 trailer:<BR/><BR/>http://people.csail.mit.edu/konak/focs_2007_trailer.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54249770834204765662007-10-19T08:44:00.000-05:002007-10-19T08:44:00.000-05:00Not every school has qualifying exams.Not every school has qualifying exams.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43785755019745285352007-10-18T22:07:00.000-05:002007-10-18T22:07:00.000-05:00Sorry,I can't find that UQED. Thanks anyway. Any ...Sorry,I can't find that UQED. Thanks anyway.<BR/> Any other students or professors in these universities can give me a hand on this?<BR/> I found that UIUC,Gatech,Wisconsin had put there qualifying exams on their theory group web,but seems others did not:-(Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10156800250426707282007-10-18T19:58:00.000-05:002007-10-18T19:58:00.000-05:00The direct link from the previous post points to s...The direct link from the previous post points to some song on YouTube.<BR/><BR/>This blog has officially hit rock bottom. Sigh.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61282985858616174602007-10-18T19:53:00.000-05:002007-10-18T19:53:00.000-05:00dammit number 9! i completely fell for that.dammit number 9! i completely fell for that.codyhttps://www.blogger.com/profile/11407919985914326282noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2886431450990024362007-10-18T09:53:00.000-05:002007-10-18T09:53:00.000-05:00All universities publish their qualifying examinat...All universities publish their qualifying examinations (if they have them) in a single online repository; the UQED (University Qualifying Exam Depository). I've embedded a direct link as follows:<BR/><BR/><A HREF="http://www.youtube.com/watch?v=eBGIQ7ZuuiU" REL="nofollow">Direct Link Here</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42138660448537121352007-10-18T09:10:00.000-05:002007-10-18T09:10:00.000-05:00hi,dear all,sorry to post an irrelevant question h...hi,dear all,sorry to post an irrelevant question here.<BR/> I wonder who can kindly give me some links of the "theory/algo qualifying exams" from univerisitys such as MIT,Princeton,Berkeley,CMU,Stanfordand Harvard(not limited to these schools).<BR/> Many thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16109656590667199712007-10-18T08:26:00.000-05:002007-10-18T08:26:00.000-05:00I'm actually not entirely sure why I find P!=NP? i...I'm actually not entirely sure why I find P!=NP? interesting, since if the answer is "TRUE", it's only a proof for a very intuitive claim, and if the answer is "FALSE", I'm pretty sure the polynom would be so big that the NP-hard problems would still remain infeasible.<BR/><BR/>I think the main reason I find it interesting is just that it sounds so intutively obvious, but still no one has been able to prove it. Okay, also P!=NP is a big assumption that the entire complexity field is built on, so it's interesting to find out if its really true, but still, I'm not sure why it's interesting in the "if someone who doesn't know anything about computer science asked me why it's interesting I could explain" kind of way.matanhttps://www.blogger.com/profile/16023846623500719671noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28364697813964542682007-10-18T04:49:00.000-05:002007-10-18T04:49:00.000-05:00Is it also true that if SAT_p is not in P then it'...Is it also true that if SAT_p is not in P then it's NP-Complete?Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87277309139502119542007-10-17T19:52:00.000-05:002007-10-17T19:52:00.000-05:00How different is the result (or the proof) from Ma...How different is the result (or the proof) from Mahaney's theorem?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6744305086125977832007-10-17T18:45:00.000-05:002007-10-17T18:45:00.000-05:00From context, interesting == worthy of attention /...From context, interesting == worthy of attention / spending time going over in class, perhaps? As for further reasoning, that's probably the question, yes? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74569434806738447702007-10-17T16:57:00.000-05:002007-10-17T16:57:00.000-05:00I think it's pretty intuitive. What do you mean by...I think it's pretty intuitive. What do you mean by interesting?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74268971610634413472007-10-17T16:44:00.000-05:002007-10-17T16:44:00.000-05:0017 is not special.See my writeup that Ipoint to. ...17 is not special.<BR/>See my writeup that I<BR/>point to. Works for any<BR/>number.<BR/><BR/>bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88793269822616201042007-10-17T16:08:00.000-05:002007-10-17T16:08:00.000-05:00For those of us who are not in the know, can you p...For those of us who are not in the know, can you please say why mod 17, rather than some other prime? Is it suspected this result is true modulo other primes or is 17 really special?Anonymousnoreply@blogger.com