tag:blogger.com,1999:blog-3722233.post117623187875298550..comments2023-02-04T09:02:15.330-06:00Comments on Computational Complexity: Knuth Prize goes to Nancy LynchLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger25125tag:blogger.com,1999:blog-3722233.post-42742675396116597692007-05-25T11:17:00.000-05:002007-05-25T11:17:00.000-05:00PLEASE HELPA little out of Context but I didnt kno...PLEASE HELP<BR/><BR/>A little out of Context but I didnt know what to do...<BR/><BR/>I have Developed an Polynomial algorithm for Graph Isomorphism and also coded it.The Conjecture is that G.I. is in P.<BR/><BR/>Now,I DESPERATELY NEED some Difficult cases of NON-ISOMORPHIC GRAPHS for testing the Algorithm that fail the current softwares and algorithms like NAUTY.<BR/><BR/>Also its my Masters Thesis and I am on a deadline..(just 3 weeks)<BR/><BR/>Can someone PLEASE PLEASE tell / help me with such Cases..<BR/><BR/>I already tried contacting Researchers but havent got any reply..<BR/><BR/>PLEASE PLEASE help me with such difficult NON-ISOMORPHIC Graphs that are Difficult to Detect ASAP..<BR/><BR/>Waiting for a response :<BR/><BR/>bharaj.tarandeep@gmail.comAnonymoushttps://www.blogger.com/profile/00993671159190945216noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176824735712049772007-04-17T10:45:00.000-05:002007-04-17T10:45:00.000-05:00Is there any translation of that "How to start you...Is there any translation of that "How to start your Ph.D. study" to English?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176712809900411622007-04-16T03:40:00.000-05:002007-04-16T03:40:00.000-05:00google "How to start your Ph.D. study", you will f...google "How to start your Ph.D. study", you will find some comments Yuanyuan Zhou made regarding the CS programs at Berkeley, Yale and Illinois. Very interesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176393853991459392007-04-12T11:04:00.000-05:002007-04-12T11:04:00.000-05:00"For instances, I know of two theories relating to..."For instances, I know of two theories relating to algorithms:<BR/>1. Computability or recursive theory, characterizing in broad sense what can be computed in principle.<BR/>2. Computational Complexity Theory, characterizing what can and can't be computed by bounded resource computations."<BR/><BR/>I said it once, and I'll say it again. Just as with computational complexity theory (which you say does constitute theory), considering any other model of computation then characterizing what can and cannot be done in *that* model should also constitute theory. Models for distributed computing are only one such example.<BR/><BR/>Furthermore, algorithmics and complexity are heavily intertwined, so to say one constitutes theory while the other doesn't seems strange. One end result of coming up with an algorithm is further understanding of the extent of your computational ability in whatever model your algorithm works in. How does this not fall under "characterizing what can and can't be computed by bounded resource computations", i.e. computational complexity theory?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176382996876830682007-04-12T08:03:00.000-05:002007-04-12T08:03:00.000-05:00Hence, I do not regard Algorithmics as pertaining ...<I>Hence, I do not regard Algorithmics as pertaining to the theory of computer-science, though it is standard to regard it as a part of TCS.</I><BR/><BR/>This is the theory as equivalent to computational complexity view, which is often derived from notions of theory-as-equivalent-to useleness-in-practice which come from mathematics.<BR/><BR/>However, to understand TCS one needs to look at physics not mathematics. Theoretical physics is defined as developments <B>relevant to physics</B> which are done on paper with mathematical tools and rigor. This stands in contrast to non-theoretical physics developments which take place in the lab.<BR/><BR/>Under this definition, logic, algorithms, machine learning, computational complexity, computabiliti theory, quantum algorithms, and approximation and parameterized algorithms among others areas fall squarely within the purview of TCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176378279489938022007-04-12T06:44:00.000-05:002007-04-12T06:44:00.000-05:00So, by definition, modeling computation in a distr...<I> So, <B>by definition</B>, modeling computation in a distributed setting and providing algorithms and impossibility results for computation in that model constitutes work in TCS.</I><BR/><BR/><BR/>Theoretical Computer-Science (TCS) is a composition of two <I>pre-defined</I> notions. So TCS is not a definition in itself, and certainly not a definition of some collective research directions and goals.<BR/><BR/>Of course, you can define a new term "TCS" to be anything you wish; Which I think is both senseless and is irrelevant to what I claimed before:<BR/>For something to becaome a <I>theory</I> it has to conform to some standards.<BR/><BR/>For instances, I know of two theories relating to algorithms:<BR/>1. Computability or recursive theory, characterizing in broad sense <I>what</I> can be computed in principle.<BR/>2. Computational Complexity Theory, characterizing what can and can't be computed by bounded resource computations.<BR/><BR/>I do not know of any other general Theory of Algorithms. Hence, I do not regard Algorithmics as pertaining to the theory of computer-science, though it is standard to regard it as a part of TCS.<BR/><BR/>Previous comments claimed that distributed computing does indeed constitute a <I>theory</I>. I am not familiar with this field, and so I will take their word for it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176316297336247502007-04-11T13:31:00.000-05:002007-04-11T13:31:00.000-05:00I don't think there is a whinier subfield in all o...<I> I don't think there is a whinier subfield in all of CS.</I><BR/><BR/>Clearly, you've never seen a full professor reduced to obscene gestures and foul language when you bring up an industrial lab that has gotten a lot of good press for alternative engineering solutions that ignore the work of him and his subfield.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176314955527941302007-04-11T13:09:00.000-05:002007-04-11T13:09:00.000-05:00deeper and abstract net of notions, assumptions, d...<I>deeper and abstract net of notions, assumptions, directions, views, explanations of certain phenomena</I><BR/><BR/>I cannot think of a better desciption for the best work in Distributed Computing.<BR/>The added bonus is that these <I>certain phenomena</I> are inherent in most computing systems of today.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176314549242216572007-04-11T13:02:00.000-05:002007-04-11T13:02:00.000-05:00To anon 15:The goal of the TCS field is to both mo...To anon 15:<BR/><BR/>The goal of the TCS field is to both model computation and describe what types of things are and are not possible in those various models. So, by definition, modeling computation in a distributed setting and providing algorithms and impossibility results for computation in that model constitutes work in TCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176313488658591822007-04-11T12:44:00.000-05:002007-04-11T12:44:00.000-05:00The FLP impossibility result was a big surprise to...The FLP impossibility result was a big surprise to many people involved in building distributed systems, even those who were quite mathematically sophisticated. I recall attending a meeting in the late 1980's a year or two after the FLP paper had appeared, at which an excellent researcher, well known for work on distributed and parallel numerical algorithms, made consistency claims for an asynchronous algorithm that directly contradicted the FLP impossibility result. When he was challenged on this by those who knew the FLP result, he still could not believe it at the meeting and was not convinced until he was walked through the details of the proof in the days after the meeting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176313186629417112007-04-11T12:39:00.000-05:002007-04-11T12:39:00.000-05:00Distributed computing is, in many ways, one of the...<I>Distributed computing is, in many ways, one of the most successful instances of /theory of computing/</I><BR/><BR/>There is a problem here with the term <I>theory</I>.<BR/><BR/>In applied fields like CS, people tend to characterize the concept of "theory" as something that is lack of immediate applications.<BR/>This interpretation is wrong in my view.<BR/><BR/>For something to become a Theory, it has to develop deeper and abstract net of notions, assumptions, directions, views, explanations of certain phenomena, etc. <BR/> I can't see how Distributed Computing is a Theory in that sense; but maybe I'm not too familiar with it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176311061875511692007-04-11T12:04:00.000-05:002007-04-11T12:04:00.000-05:00Distributed computing is, in many ways, one of the...Distributed computing is, in many ways, one of the most successful instances of /theory of computing/ in the sense that it is first-rate theory that relates (and affects) computing.<BR/><BR/>In that respect, this area shows the impact of Nancy Lynch in combining solid theoretical foundations, clever mathematics (yes...), and ramifications for real systems.<BR/><BR/>The other area that has similar achievements is database theory (and indeed, some of the past winners have been involved in database theory). <BR/>This area used to have good STOC/FOCS representation, but it was marginalized, and it is the loss of the TCS community.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176309980571961532007-04-11T11:46:00.000-05:002007-04-11T11:46:00.000-05:00Whiners, the Knuth prize award "may also be partly...Whiners, the Knuth prize award "may also be partly based on educational accomplishments and contributions such as fundamental textbooks and high-quality students". Apart from Yao and Ajtai, all the other past recipients not only possess a "sustained record of high-impact, seminal contributions to the foundations of computer science", as required, but have published books that are real gems.D. Sivakumarhttps://www.blogger.com/profile/05750992965116762335noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176306277917505622007-04-11T10:44:00.000-05:002007-04-11T10:44:00.000-05:00I don't think there is a whinier subfield in all o...<I>I don't think there is a whinier subfield in all of CS.<BR/></I><BR/><BR/>Again, the problem is that TCS, by which I am mainly referring to computational complexity theory, is by large part, a vivid subfield of mathematics. Applied CS, is a vivid part of engineering.<BR/>Therefore, this kind of negative debate is going to continue, as both fields have different goals, different tastes, different motivations, different techniques and so forth.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176300375725644302007-04-11T09:06:00.000-05:002007-04-11T09:06:00.000-05:00My "favorite" is when the award recipient shit-tal...My "favorite" is when the award recipient shit-talks about the award committee.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176285360875954612007-04-11T04:56:00.000-05:002007-04-11T04:56:00.000-05:00How come whenever an award is announced on this bl...<I> How come whenever an award is announced on this blog, there's always a ton of TCSers shit-talking about the awardee</I><BR/><BR/>I totally agree with the previous comment. Those shit-talking people are thousands of years far from getting any of these awards. Maybe this explains why they can only say "this is not deep" or "that is not mathematical".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176278155839107362007-04-11T02:55:00.000-05:002007-04-11T02:55:00.000-05:00How come whenever an award is announced on this bl...How come whenever an award is announced on this blog, there's always a ton of TCSers shit-talking about the awardee (e.g. Knuth Prize and Turing Award)? I don't think there is a whinier subfield in all of CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176259127341507842007-04-10T21:38:00.000-05:002007-04-10T21:38:00.000-05:00It seems a lot of people confuse "depth" for "math...It seems a lot of people confuse "depth" for "mathematical sophistication". IMO, what should matter in our community is "computational depth", in the sense that we should value a result if it exposes or explains something that is either fundamental or has wide ranging implications in our understanding of computation.<BR/><BR/>I don't really care whether a theorem is proved using combinatorics, algebra or topology. What I care about is the result, and what it means about computation. If the mathematics used are "sophisticated" then great (especially if it means we can use new machinery), but I don't believe we should judge a result on this basis.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176253149242998882007-04-10T19:59:00.000-05:002007-04-10T19:59:00.000-05:00FLP is just a big nasty adversarial argument. It's...FLP is just a big nasty adversarial argument. It's nothing to do with topology. At least not by the time when it was published. But the truly original contribution of FLP is seeing distributed computing as state transitions, which is now as obvious as falling apples, or entropy of information. I guess the true meaning of a life-time award is not how deep the awardee's work is, but a nowaday common sense is first introduced by him/her.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176251660734443682007-04-10T19:34:00.000-05:002007-04-10T19:34:00.000-05:00Distributed computing, or more precisely Concurren...Distributed computing, or more precisely Concurrency Theory, has developed deep connections with abstract homotopy theory (in the sense of Quillen), and this is as deep you can get in contemporary mathematics. Having said this, I do not know if Nancy Lynch's work has anything to do with these developments, other than introducing some basic topological concepts to the area.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176249731497163572007-04-10T19:02:00.000-05:002007-04-10T19:02:00.000-05:00"Mathematical depth means making connections no on..."Mathematical depth means making connections no one ever made before"<BR/><BR/>That's cute. But no, I'm sorry, it doesn't.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176243478604388182007-04-10T17:17:00.000-05:002007-04-10T17:17:00.000-05:00There's a topic for your blog, Bill -- Mathematica...There's a topic for your blog, Bill -- Mathematical Depth! Dear Anonymous 3: Mathematical depth means making connections no one ever made before, not producing a turgid proof. NP means easily verifiable. Feynmann used to say that if we couldn't explain concepts to advanced undergraduates, we didn't really understand them at all. Nancy L's book reads like a dream. Such exposition requires extremely advanced mathematical sophistication. Anybody can present something that's too hard to understand.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176240875154643372007-04-10T16:34:00.000-05:002007-04-10T16:34:00.000-05:00Hmph, does distributed computing really count as T...Hmph, does distributed computing really count as TCS?? Even this famous FLP result is not mathematically deep.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176239401977176892007-04-10T16:10:00.000-05:002007-04-10T16:10:00.000-05:00The prize is awarded every year and a half because...The prize is awarded every year and a half because it is a joint award between ACM-SIGACT, which sponsors STOC, and IEEE-TCMFC, which sponsors FOCS. This way it can be awarded alternately at STOC and FOCS. The other solution would have been to give out two every year, but that seemed too frequent for a lifetime achievement award.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1176233543786219532007-04-10T14:32:00.000-05:002007-04-10T14:32:00.000-05:00who came up with the one every 1.5 years schedule?...who came up with the one every 1.5 years schedule? And just why on earth did they choose to do it that way?Anonymousnoreply@blogger.com