tag:blogger.com,1999:blog-3722233.post7568750405063097266..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Lets Congradulate Gerard Huet! (who?)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-34134057363076684172009-04-07T15:20:00.000-05:002009-04-07T15:20:00.000-05:00Probably CMU is on the other side of the river :)Probably CMU is on the other side of the river :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21639018321735052372009-03-11T07:07:00.000-05:002009-03-11T07:07:00.000-05:00Pascal Koiran asked: What about other examples ? A...Pascal Koiran asked: <BR/><BR/><I>What about other examples ?</I> <BR/><BR/>Another possible example, which may also relate to the very interesting problem raised by Semanticist, is the study of logical approaches to ensure complexity bounds on lambda-calculus or functional programs. See, for instance, the web page for this <A HREF="http://www-lipn.univ-paris13.fr/~baillot/GEOCAL06/complexitylecture.html" REL="nofollow">course</A>. I am sure that a lot has happened since 2006 in this area, and the experts will be able to point out recent developments. <BR/><BR/>The whole field of descriptive complexity links logic and complexity theory in a way that I have always found beautiful. <BR/><BR/>In the field of networking, <A HREF="http://doi.acm.org/10.1145/1282380.1282405" REL="nofollow">this paper</A> offers an application of formal semantics to formally analyze network protocols based on structural properties, and also to derive working prototype implementations of these protocols. <BR/><BR/>The whole field of model checking in based on the rich interplay between logic, models of computation and algorithms. <BR/><BR/>Connections between logic, graphs and algorithms are described in, e.g., <A HREF="http://www2.informatik.hu-berlin.de/~grohe/pub/meta-survey.pdf" REL="nofollow">this survey paper</A> by Martin Grohe. <BR/><BR/>I am sure the list could go on and on. One just has to keep and open mind, and look for the connections.Luca Acetohttps://www.blogger.com/profile/01092671728833265127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23381836602569998272009-03-10T18:39:00.000-05:002009-03-10T18:39:00.000-05:00Treewidth and related notions such as query width ...Treewidth and related notions such as query width come up in both algorithms and logic.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23899641789930675582009-03-10T16:48:00.000-05:002009-03-10T16:48:00.000-05:00Michael Mitzenmacher in comment 3 and Semanticist ...Michael Mitzenmacher in comment 3 and Semanticist in comment 11 make very good points.<BR/>There is at least one recent example showing some convergence betweeen the two sides of TCS : in cryptography, there has been some work connecting computational complexity based crypto to the more "semantic" approach from the Dolev-Yao model.<BR/>(I can already hear the screams: "wait a minute, I thought Yao belonged to us!!")<BR/><BR/>What about other examples ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56421721266650519812009-03-10T16:20:00.000-05:002009-03-10T16:20:00.000-05:00FFT's are a bad example to cite since it aboslutel...FFT's are a bad example to cite since it aboslutely has not been ignored. Martin Furer recently improved the complexity of the best algorithm for integer multiplication (based on FFT's) and this recently won a best paper award at STOC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67067746290311506762009-03-10T15:08:00.000-05:002009-03-10T15:08:00.000-05:00Semanticist wrote: "The extrinsic viewpoint ignore...Semanticist wrote: "The extrinsic viewpoint ignores the intrinsic viewpoint and vice versa."<BR/><BR/>Perhaps normalization by evaluation offers a link between the two viewpoints you have in mind? Should I get around to rising to Michael's invitation for a guest blog post, what I write would definitely mention NBE.單中杰https://www.blogger.com/profile/14754929367418830739noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48090044940814554252009-03-10T13:16:00.000-05:002009-03-10T13:16:00.000-05:00Pardon my ignorance. But could please you explain ...<I>Pardon my ignorance. But could please you explain why you think people should work on complexity of FFT or Matrix multiplication, and not on PCPs? </I><BR/><BR/>I don't want to sound very flippant but just consider the number of matrices being multiplied and FFT's being computed every millisecond, with the number of PCP's that have been constructed since the time they were defined.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68593399403897798782009-03-10T09:39:00.000-05:002009-03-10T09:39:00.000-05:00People in US TCS are paper machines.Some of them r...People in US TCS are paper machines.<BR/>Some of them regularly have 4 or<BR/>5 FOCS/STOC/SODA papers in one year<BR/>and are pride of that. <BR/>That is why they donot study exponent<BR/>of matrix multiplication or integer factorization, but PCP.<BR/>Otherwise there are simply not<BR/>many papers to write.<BR/><BR/>In more serious science, if you write<BR/>too many papers, your colleagues<BR/>will look at you with suspicious.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24064531267158964232009-03-10T09:32:00.000-05:002009-03-10T09:32:00.000-05:00L. Aceto wrote: "We should inspire our students to...L. Aceto wrote: "We should inspire our students to have a holistic view of (T)CS and build an appreciation for both volume A and volume B research as well as for the work of the giants of our field, who are by and large still active and inspirational figures one can meet by attending conferences, workshops and other meetings."<BR/><BR/>I think the problem is much deeper than a mere lack of attention. Semantics on the one hand and complexity/algorithms on the other look at computation from very different angles: Semantics looks at computation by paying attention to intrinsic program structure. Complexity/algorithms look at computation from the outside, by counting the number of execution steps, number of memory cells used. THe extrinsic viewpoint ignores the intrisic viewpoint and vice versa. But this lack of attention to the other viewpoint is because of a deep technical difficulty: there are no known (or hardly any) known connections between the two points of view, and that's despite computational intuition suggesting that there should be.<BR/><BR/>I think forging a technical connection between the two is a deep open problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92213813903147055922009-03-10T09:25:00.000-05:002009-03-10T09:25:00.000-05:00"I happen to be from the "other branch", where peo..."I happen to be from the "other branch", where people hold Huet in the same view as, perhaps, you may hold Karp."<BR/><BR/>Karp who?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13640646459003566242009-03-10T06:57:00.000-05:002009-03-10T06:57:00.000-05:00Bill, I have the feeling that you meant well by wr...Bill, I have the feeling that you meant well by writing this post, but your choice of title and some of the prefatory text might have given a different impression to some of your readers. The blog medium can be very unforgiving at times and some of the comments that are sometimes aired on the very interesting blogs in your blog roll I read with some regularity do seem to indicate the "lack of knowledge/acknowledgment of our side of the river" Avik referred to in his well worded comment to this post.<BR/><BR/>First of all, let me stress that the EATCS is an international organization that covers the whole spectrum of TCS. This means that the prizes and awards it sponsors are meant to reflect, at least in principle, work that is done in <I>any</I> area of TCS, broadly construed.<BR/><BR/>TCS is a wide field and, in general, we cannot keep track of the details of the work or the latest advances in areas outside our specializations. However, I feel that a well read TCS researcher ought to have at least a little appreciation of the general type of results and contributions, and of the people behind them, in other sub-fields of our beautiful subject. Just attending seminars in areas of TCS we do not work on, or reading general introductory pieces on work done in those areas, can help a lot in this respect. We should inspire our students to have a holistic view of (T)CS and build an appreciation for both volume A and volume B research as well as for the work of the giants of our field, who are by and large still active and inspirational figures one can meet by attending conferences, workshops and other meetings.<BR/><BR/>This is the reason why, while I fully understand Michael's "utilitarian" comment:<BR/><BR/><I>I think that lack of knowledge often (albeit not always) corresponds to lack of utility. I'm open to using techniques from other fields -- statistics and information theory -- for work in randomized algorithms. But I haven't been made aware of how knowledge of "the other side" could benefit my work.</I><BR/><BR/>I tend to disagree with it a little. I like to think that, in an ideal world, we should all have a little motivation to develop a passing acquaintance with the "other" (I was about to write, the "dark" :-)) side because of intellectual curiousity.<BR/><BR/>Coming back to Huet and to whether his line of research is not represented in America, let me say that, together with some other colleagues, I had submitted a competing nomination for the EATCS award. Of course, I would have liked to see my nomination succeed. However, there was never any doubt in my mind that Huet is a worthy recipient of the EATCS award and, as a member of the EATCS Council, I supported the decision of the prize committee without hesitation when it was announced to the Council.<BR/><BR/>A look at the list of signatories for Huet's nomination shows immediately that his work is held in high esteem by very distinguished theoretical computer scientists in America, Asia and Europe, including a Turing Award winner the highlights of whose work, I feel, should be known, at least by name, by <I>any</I> member of the TCS community.<BR/><BR/>Also I do not think that it is fair or productive to say that Huet's line of work is not popular in North America when people like Bob Constable, Dale Miller, Frank Pfenning and Benjamin Pierce are amongst those singing his praises. (OK, Dale is now based in France with his wife Catuscia Palamidessi, but he is a born and bred American researcher.) There is a lot of excellent work done in America in TCS on topics that these days are not typically covered by conferences like FOCS, SODA and STOC.<BR/><BR/>As Avik put it in his closing sentence<BR/><BR/><I>I would advise...people to also check out LICS/POPL/ICFP/CSF... and the world of theory might suddenly seem much cooler.</I><BR/><BR/>I do not know about the "coolness factor", but certainly the world of TCS would look as broad, fascinating and multi-faceted as it really is. Wouldn't this be a good thing? I strongly believe so.Luca Acetohttps://www.blogger.com/profile/01092671728833265127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-926813096792315362009-03-09T22:48:00.000-05:002009-03-09T22:48:00.000-05:00The research on this side of the river (Atlantic O...<I>The research on this side of the river (Atlantic Ocean ?) <BR/>except for an occasional gem, has degenerated into little paper-producing industries of various sorts -- game theory, economics, e-commerce, <BR/>World Wide Web, PCP's etc. -- while the truly old and venerable problems of theoretical CS, such as P/NP, exponent of matrix multiplication, better factoring algorithms, true complexity of the FFT to name a few, remain mostly untouched (except perhaps by some hermit types working away in Siberia ...)<BR/></I><BR/><BR/>Pardon my ignorance. But could please you explain why you think people should work on complexity of FFT or Matrix multiplication, and not on PCPs?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3378653396774952042009-03-09T22:27:00.000-05:002009-03-09T22:27:00.000-05:00My first published paper was in concurrency. I thi...My first published paper was in concurrency. I think in the world of multicore processing, understanding of logic, program proving, etc is very useful.<BR/><BR/>Michael, of course what some of us are currently working on, may not have much utilization of the work done on the eastern side of the pond. But a possible reason could be a narrow focus, if it is, of our work.<BR/><BR/>I think one of the problems which keep some of Microsoft's leaders awake is finding a right programming paradigm for multicore processors. I think work in logic programming has some notion of efficiency in case of an algorithm is at least partly asynchronous. Currently if you have a quad core machine, it is likely that a core is not fully used, whereas there is a lot of work which your computer could do for you.<BR/><BR/>The notion of correctness is different, the notion of efficiency is diffent, and testing of programs is hard in case of asynchronous programming world. BTW, testing of programs is an algorithmic question.<BR/><BR/>There is a lot of work done on these subjects in the past, especially in high performance programming. I think there is a lot remaining which will be needed, since this kind of processing power will be available to masses. People who pursue this line of work, may need to utilize the TCS concepts from both sides of the pond (and of course of both sides of the other bigger pond too).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16073392651007573622009-03-09T21:23:00.000-05:002009-03-09T21:23:00.000-05:00Have to agree with anon 1. They gotta make America...Have to agree with anon 1. They gotta make Americans take the TOEFL with foreign grad students!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36200210169990156692009-03-09T18:53:00.000-05:002009-03-09T18:53:00.000-05:00This is not to say anything negative about the fie...<I>This is not to say anything negative about the field -- I also don't know how chemistry would help my work, but there's a lot positive to say about chemistry.</I><BR/><BR/>Chemistry is heavily studied in the US. But why is this other branch of TCS not heavily studied in the US?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92115489908931067582009-03-09T18:50:00.000-05:002009-03-09T18:50:00.000-05:00I'm sure P =/= NP is an important question, and I ...<I>I'm sure P =/= NP is an important question, and I realize SODA/FOCS mean the world to some people ...<BR/></I><BR/>You give too much credit to people on "this side" of the river. In reality very few (if at all any) of the people who regularly publish in SODA/FOCS devote any time to P vs. NP (other than on occasions when they feel it necessary to put forth eloquently on the <BR/>greatness and depth of their subject). Otherwise, I would have expected some discussions on this blog about the merits/demerits of say Mulmuley's program following his lectures in Princeton. The research on this side of the river (Atlantic Ocean ?) <BR/>except for an occasional gem, has degenerated into little paper-producing industries of various sorts -- game theory, economics, e-commerce, <BR/>World Wide Web, PCP's etc. -- while the truly old and venerable problems of theoretical CS, such as P/NP, exponent of matrix multiplication, better factoring algorithms, true complexity of the FFT to name a few, remain mostly untouched (except perhaps by some hermit types working away in Siberia ...)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70025984075906986652009-03-09T18:24:00.000-05:002009-03-09T18:24:00.000-05:00Avik --I think that lack of knowledge often (albei...Avik --<BR/><BR/>I think that lack of knowledge often (albeit not always) corresponds to lack of utility. I'm open to using techniques from other fields -- statistics and information theory -- for work in randomized algorithms. But I haven't been made aware of how knowledge of "the other side" could benefit my work. <BR/><BR/>This is not to say anything negative about the field -- I also don't know how chemistry would help my work, but there's a lot positive to say about chemistry. <BR/><BR/>I'd certainly be happy to have the situation rectified. You're welcome to guest post on my blog about how tools and techniques from logic, programming languages, theorem proving, etc. would be useful to someone working in networks, randomized algorithms, information theory, or other related fields. (And that's a general open invitation -- guest posts are welcome.)Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10469979207564890602009-03-09T13:41:00.000-05:002009-03-09T13:41:00.000-05:00Unfortunately, it seems to happen too often that, ...Unfortunately, it seems to happen too often that, while there are two branches of TCS (one of which includes, e.g., algorithms, complexity, ... and the other includes. e.g., logic, programming languages, theorem proving, ...), several people in the former branch seldom seem to know/acknowledge that the other branch exists.<BR/><BR/>In fact, this sorry state of affairs may have existed since Turing and Church! ("Do you think in terms of bits or in terms of lambdas?")<BR/><BR/>I happen to be from the "other branch", where people hold Huet in the same view as, perhaps, you may hold Karp. (Some of us regularly check their proofs with Coq before submitting papers.) <BR/><BR/>While I was an undergrad, I had the fortune of spending a summer at INRIA doing an internship with Huet. Curiously, he seemed to have, just like most of his colleagues on this side of the river, a much deeper appreciation for the other side. (He actually used a lot of automata theory for his later work.)<BR/><BR/>I regularly read your blog, as well as some of the others' in your blogroll (Scott's, Mihai's, Michael's, ...) In at least some of these blogs (guess?), I keep getting disappointed with the lack of knowledge/acknowledgment of our side of the river. I find this amusing as well as embarassing.<BR/><BR/>I'm sure P =/= NP is an important question, and I realize SODA/FOCS mean the world to some people, but I would advise such people to also check out LICS/POPL/ICFP/CSF... and the world of theory might suddenly seem much cooler.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60915919078272818152009-03-09T11:25:00.000-05:002009-03-09T11:25:00.000-05:00"Congratulate" is spelled with a t."Congratulate" is spelled with a t.Anonymousnoreply@blogger.com