Janos Simon and Luca Trevisan are reporting from FOCS 2006 (Berkeley, CA)---a conference from which our community is, alas, conspicuously absent---on the Complexity Blog and on In Theory, respectively. Their live reports make for very interesting reading. I encourage you to read Janos's report on the FOCS Business Meeting to get an idea of the state of funding for TCS in the US.
One of the events at FOCS was a concert by Lady X and The Positive Eigenvalues, a band that includes Christos Papadimitriou on keyboards. As Luca Trevisan notes in his blog, apart from Christos Papadimitriou, Mike Jordan, and guest star Anna Karlin, that band includes "a number of other Berkeleites (for some reason, all Italians)."
This is not the first ever example of a rock concert held at a major theory conference. I recall that Dexter Kozen and his band performed at the Monterey aquarium during LICS 1989. Amongst others, they offered (T)CS renditions of songs by the Ramones (I wanna be promoted) and the Dead Kennedys (Categories über alles). At the time I collected a leaflet with the text of the songs Dexter's band played, but I lost it. Here is a scanned version of the leaflet, courtesy of Don Sannella. Enjoy it!
Wednesday, October 25, 2006
Sunday, October 22, 2006
Report on NWPT06
Anna and I organized the 18th Nordic Workshop on Programming Theory from Wednesday, 18 October, till Friday, 20 October, at Reykjavík University. The workshop was held under the auspices of the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS) and of the IFIP TC1 Working Group 1.8 on Concurrency Theory, and was partly sponsored by Reykjavík University.
The NWPT series of annual workshops is a forum bringing together programming theorists from the Nordic and Baltic countries (but also elsewhere). The previous workshops were held in Uppsala (1989, 1999 and 2004), Aalborg (1990), Gothenburg (1991 and 1995), Bergen (1992 and 2000), Turku (1993, 1998, and 2003), Aarhus (1994), Oslo (1996), Tallinn (1997 and 2002), Lyngby (2001), and Copenhagen (2005). Thus, this was the first ever NWPT workshop held in Iceland.
- There were no contributed talks from Sweden, and David Sands was therefore the only representative of Swedish computer science at the workshop.
- There was a good number of participants from Germany.)
- Gerd Behrmann, Aalborg University. How to become a successful tool builder - the dirty tricks
- Matthew Hennessy, University of Sussex. Some Remarks on Testing Probabilistic Processes.
- Hanne Riis Nielson, DTU. Analysis of Process Interactions
- David Sands, Chalmers University of Technology and University of Göteborg. Specifying and Verifying Dynamic Information Flow Properties
Gerd Behrmann's talk offered a thought provoking and stimulating analysis of the role of tool development in algorithmic verification. Gerd gave the audience many good reasons for building tools, but also pointed out that empirical studies in this field are often of questionable quality, with results that are not reproducible and unfounded conclusions. He pledged for this situation to be improved if tool building is to become a respected scientific activity.
Not surprinsingly, Gerd's talk gave rise to a lively discussion (both during and after the presentation). Flemming Nielson made some very interesting remarks after the talk, explaining how a tool developer can obtain credit for his/her work at his institution (DTU), e.g., by means of innovation schemes and the writing of books about the lessons learned during tool building. He also defended, in case there was any need to do so, the hard work of theorists, and uttered the following eminently quotable sentence:
"The purpose of theory is insight, not theorems!"
Matthew Hennessy delivered a talk on testing probabilistic processes that presented work he did while visiting NICTA in Australia. This was a one hour version of a shorter talk he had delivered earlier at the symposium in honour of Gordon Plotkin's sixtieth birthday. Matthew gave a typically well polished lecture, which managed to present a lot of technical work without ever giving his audience the feeling of being overwhelmed by the mathematics. I am looking forward to reading the paper on which the talk was based.
The last invited talk for the workshop was delivered by David Sands. Static verification of secure information flow has been a popular theme in recent programming language research, but the information flow policies considered are based on a static view of security levels. In his talk, Dave provided a road map of the main directions of current research, and introduced a simple mechanism, called flow locks, for specifying dynamic information flow policies, and a type-and-effect system for statically verifying flow lock policies. The talk was based on joint work with Niklas Broberg.
The 26 contributed talks were mostly of excellent quality, presenting work at different stages of development; some of it was definitely in progress, some other was "in infancy", and some was instead very mature. This is what a workshop should be like!
Some photos from the workshop, courtesy of MohammadReza Mousavi, are available.
The 2007 edition of the workshop will be held in Oslo, Norway. I trust that it'll be just as successful as we felt this one was. Good luck to Olaf Owe, who will take over the mantle of organizer from Anna and me.
Tuesday, October 17, 2006
Double Blind Refereeing
A colleague of ours was discussing the following dilemma with Anna today.
A computer scientist is preparing a submission to a conference in Language Technology that has double blind refereeing. He is just about the only person in the world doing tagging for Icelandic. Should he cite his own work in the submission?
This colleague realized that, by citing his own work, he would make his identity known to the reviewers, and was worried that this might influence them. We told him that a reviewer would be able to infer the name of the author from the paper anyway because he is really the only possible author of that paper. (In general, in TCS the set of possible authors of a paper is not very large, and, using tell-tale stylistic or notational usages, a reviewer of an authorless paper is often able to determine the author(s) of a paper with a rather large degree of accuracy.)
Consider also the following catch-22 situation. A reviewer of the paper by our colleague could reject it because the anonymous author X is neither citing the closely related work of author X nor comparing his work with that of author X! It would be just great to have one's paper rejected for not citing one's own work, wouldn't it?
I have never believed in double blind refereeing. This story has reinforced my lack of belief in this system.
A computer scientist is preparing a submission to a conference in Language Technology that has double blind refereeing. He is just about the only person in the world doing tagging for Icelandic. Should he cite his own work in the submission?
This colleague realized that, by citing his own work, he would make his identity known to the reviewers, and was worried that this might influence them. We told him that a reviewer would be able to infer the name of the author from the paper anyway because he is really the only possible author of that paper. (In general, in TCS the set of possible authors of a paper is not very large, and, using tell-tale stylistic or notational usages, a reviewer of an authorless paper is often able to determine the author(s) of a paper with a rather large degree of accuracy.)
Consider also the following catch-22 situation. A reviewer of the paper by our colleague could reject it because the anonymous author X is neither citing the closely related work of author X nor comparing his work with that of author X! It would be just great to have one's paper rejected for not citing one's own work, wouldn't it?
I have never believed in double blind refereeing. This story has reinforced my lack of belief in this system.
Friday, October 13, 2006
Mini Course on Model Checking Real-time Systems in Reykjavík
As part of the ICE-TCS activities held during the coming week, which will be mostly devoted to the 18th Nordic Workshop on Programming Theory, we shall host a mini course Model Checking for Real-time Systems held by Kim G. Larsen. The course will be held on Monday, 16 October, at Reykjavík University. (In case you are interested in looking at some text in Icelandic, you can see the announcement that will appear tomorrow in one of the local newspapers.)
The course will be followed by an exercise session on Tuesday, 17 October, held by Alexandre David (Aalborg University). Feel free to drop by, if you happen to be in Reykjavík for the Iceland Airwaves music festival.
The course will be followed by an exercise session on Tuesday, 17 October, held by Alexandre David (Aalborg University). Feel free to drop by, if you happen to be in Reykjavík for the Iceland Airwaves music festival.
Teaching Reductions
This semester I am teaching Introduction to the Theory of Computation at Reykjavík University, a course taken by third year BSc students and MSc students alike. I like teaching this course (based on Michael Sipser's book bearing the same title) very much, and I try to convey to the students the intellectual excitement I feel about the theory of automata, computability and complexity.
After last Wednesday's lecture, however, I was totally drained of energy. Why? During Tuesday's lecture I introduced the concept of reduction, and used it to prove the undecidability of the emptiness, equality and regularity problem for Turing machines. The day after I started the lecture with a warm-up, peer instruction session asking the students to argue that it is undecidable whether a Turing machine accepts the language {Alan, Turing}. The reaction was summarized by the blank stare I got from most of my audience Even when we worked through the solution together, I still had the feeling that many of them were not comfortable with the notion of reduction. I had to work very hard to try and clarify it as best as I could, and it is not clear to me yet whether I succeeded.
Looking back to my previous experiences teaching this course, or variations on it, in Aalborg, this is not surprising. The notion of reduction is the bread-and-butter of computability and complexity, and one of the cornerstones of algorithmic thinking. Having mastered it, the rest of the material in my introductory courses becomes, I would venture to say, relatively easy. It is one of those powerful concepts that opens up new vistas, and, despite being very natural and ubiquitous in the theory of computing, requires some intellectual maturity to be understood fully.
A typical pitfall I have experienced over the years is that many students think that the pre-processing algorithm converting, say, the question "Does a Turing machine M accept the string w?" into an equivalent one of the form "Does the Turing machine M' accept the empty language?" actually runs M on input w when, while producing the code for M', it writes the line of code
Run M on input w.
Here I usually use the analogy with a compiler to try and dispel their doubts. (Basically, I tell them to view the pre-processing algorithm implementing the reduction as a compiler between inputs to two different problems. The pre-processing algorithm outputs a piece of code, but never runs it.) It is not up to me to say whether this works, but it seems to me that most of the students "crack the code", and start thinking naturally in terms of reductions between algorithmic problems.
Is it just my personal experience, or are reductions hard to grasp for many of our students? I'd be happy to hear how you go about teaching reductions in your classes on the theory of computation, and what analogies/metaphors you use to help your students understand such a fundamental notion.
After last Wednesday's lecture, however, I was totally drained of energy. Why? During Tuesday's lecture I introduced the concept of reduction, and used it to prove the undecidability of the emptiness, equality and regularity problem for Turing machines. The day after I started the lecture with a warm-up, peer instruction session asking the students to argue that it is undecidable whether a Turing machine accepts the language {Alan, Turing}. The reaction was summarized by the blank stare I got from most of my audience Even when we worked through the solution together, I still had the feeling that many of them were not comfortable with the notion of reduction. I had to work very hard to try and clarify it as best as I could, and it is not clear to me yet whether I succeeded.
Looking back to my previous experiences teaching this course, or variations on it, in Aalborg, this is not surprising. The notion of reduction is the bread-and-butter of computability and complexity, and one of the cornerstones of algorithmic thinking. Having mastered it, the rest of the material in my introductory courses becomes, I would venture to say, relatively easy. It is one of those powerful concepts that opens up new vistas, and, despite being very natural and ubiquitous in the theory of computing, requires some intellectual maturity to be understood fully.
A typical pitfall I have experienced over the years is that many students think that the pre-processing algorithm converting, say, the question "Does a Turing machine M accept the string w?" into an equivalent one of the form "Does the Turing machine M' accept the empty language?" actually runs M on input w when, while producing the code for M', it writes the line of code
Run M on input w.
Here I usually use the analogy with a compiler to try and dispel their doubts. (Basically, I tell them to view the pre-processing algorithm implementing the reduction as a compiler between inputs to two different problems. The pre-processing algorithm outputs a piece of code, but never runs it.) It is not up to me to say whether this works, but it seems to me that most of the students "crack the code", and start thinking naturally in terms of reductions between algorithmic problems.
Is it just my personal experience, or are reductions hard to grasp for many of our students? I'd be happy to hear how you go about teaching reductions in your classes on the theory of computation, and what analogies/metaphors you use to help your students understand such a fundamental notion.
Monday, October 09, 2006
Turing in the Notices of the AMS
The November issue of the Notices of the AMS is entirely devoted to Alan Turing. (I first learned about this issue via Luca Trevisan's blog in theory.) I have only had time to skip through Solomon Feferman's piece on Turing's thesis (his PhD thesis, not the Church-Turing thesis), but the whole issue looks very interesting.
I have already recommended it to the students who are taking my theory of computation course in Reykjavík.
Enjoy it!
I have already recommended it to the students who are taking my theory of computation course in Reykjavík.
Enjoy it!
Wednesday, October 04, 2006
Paul Halmos, 1914-2006
I just saw a sad news item on the AMS web site. Paul Halmos passed away on Monday, 2 October. He was a master of mathematical exposition, both in writing and speaking, and taught many writers in the mathematical sciences how to write.
A few years ago, I had the pleasure of borrowing his "mathobiography" I Want to Be a Mathematician from Steffen Lauritzen in Aalborg, and enjoyed it immensely. I plan to buy a copy for my bookshelves at some point.
Bas Luttik has keeps telling me to read Halmos's expository work on algebraic logic. I keep postponing doing so, but maybe now it is time to start. At least after some pencil sharpening has taken place :-)
Let me end with a quotation from Halmos's mathobiography I like:
These days I sharpen my pencils a lot, alas.
A few years ago, I had the pleasure of borrowing his "mathobiography" I Want to Be a Mathematician from Steffen Lauritzen in Aalborg, and enjoyed it immensely. I plan to buy a copy for my bookshelves at some point.
Bas Luttik has keeps telling me to read Halmos's expository work on algebraic logic. I keep postponing doing so, but maybe now it is time to start. At least after some pencil sharpening has taken place :-)
Let me end with a quotation from Halmos's mathobiography I like:
"I love to do research, I want to do research, I have to do research, and I hate to sit down and begin to do research---I always try to put it off just as long as I can.
....Isn't there something I can (must?) do first? Shouldn't I sharpen my pencils perhaps?"- --Paul Halmos, I Want to be a Mathematician
These days I sharpen my pencils a lot, alas.
Saturday, September 30, 2006
N is a Number
Yesterday, ICE-TCS hosted its first movie event with the projection of the documentary film N is a Number: A Portrait of Paul Erdös by George Csicsery. I bought the DVD of this award winning documentary using my Springer author discount, and, rather than watching it at home, I decided to share it with my colleagues at Reykjavík University. I also hoped that some of our students would show up to watch the documentary. (Every opportunity is good to entice students to study TCS! Unfortunately, however, no student took the bait and joined us :-()
The documentary is good and I recommend it, even though it does not hold many surprises for people who have read the popular books on Paul Erdös. However, watching Paul Erdös strut his skills on the dias before diving into the mathematics was an enjoyable experience for somebody like me who never had the chance of seeing him "live".
I wonder whether he is still managing to keep the SF's score low wherever he may be now.
Addendum: The Erdös numbers of the members of ICE-TCS are here.
The documentary is good and I recommend it, even though it does not hold many surprises for people who have read the popular books on Paul Erdös. However, watching Paul Erdös strut his skills on the dias before diving into the mathematics was an enjoyable experience for somebody like me who never had the chance of seeing him "live".
I wonder whether he is still managing to keep the SF's score low wherever he may be now.
Addendum: The Erdös numbers of the members of ICE-TCS are here.
Sunday, September 24, 2006
MohammadReza Mousavi in Reykjavík
Albeit belatedly, due to some last minute bureacratic hassles arising from the lack of experience of the staff at a young university like Reykjavík University, MohammadReza Mousavi has joined our little concurrency theory group at Reykjavík University. Anna and I are understandably thrilled at having him here. Mohammad will have a joint position between Reykavík University and TU Eindhoven.
The 'group' has doubled in size since August this year, with the arrival of Silvio Capobianco (a mathematician from Rome) and Mohammad. Their arrival has also strengthened ICE-TCS considerably, and their presence is giving Anna and me a good intellectual environment to work in. Now it's up to us to make the most of this opportunity, and I hope that we'll be able to capitalize on their scientific strength. If we don't, then it's going to be solely our fault.
The problems we encountered in getting a visa for Mohammad at the last minute seem to have some positive consequences. Together with the Icelandic research council, we are pressing the politicians here to establish a fast-track for researchers seeking visas and work permits to come and work in Iceland. Having a "researcher visa" procedure might make it more attractive for scientists to come and work here in the North Atlantic, at times when access to other countries is becoming more and more difficult. I'll keep you posted on the developments.
The 'group' has doubled in size since August this year, with the arrival of Silvio Capobianco (a mathematician from Rome) and Mohammad. Their arrival has also strengthened ICE-TCS considerably, and their presence is giving Anna and me a good intellectual environment to work in. Now it's up to us to make the most of this opportunity, and I hope that we'll be able to capitalize on their scientific strength. If we don't, then it's going to be solely our fault.
The problems we encountered in getting a visa for Mohammad at the last minute seem to have some positive consequences. Together with the Icelandic research council, we are pressing the politicians here to establish a fast-track for researchers seeking visas and work permits to come and work in Iceland. Having a "researcher visa" procedure might make it more attractive for scientists to come and work here in the North Atlantic, at times when access to other countries is becoming more and more difficult. I'll keep you posted on the developments.
Friday, September 22, 2006
New Perspectives on Fairness
I have just posted the concurrency column for the October 2006 installement of the Bulletin of the EATCS. The October column is a lovely piece entitled New Perspectives on Fairness by Daniele Varacca and Hagen Voelzer.
Fairness is an important concept that appears repeatedly in various forms in different areas of computer science, and plays a crucial role in the semantics and verification of reactive systems. Entire books are devoted to the notion of fairness---see, for instance, the monograph by Nissim Francez published in 1986---, and researchers in our community have painstakingly developed a taxonomy of various fairness properties that appear in the literature, such as unconditional fairness, weak fairness, strong fairness, and so on. This research is definitely important in light of the plethora of notions of fairness that have been proposed and studied in the literature.
But when is a temporal property expressing a fairness requirement? The authors of this column have recently developed a very satisfying answer to this fundamental question by offering three equivalent characterizations of ``fairness properties'' in the setting of linear-time temporal logic: a language-theoretic, a topological, and a game-theoretic characterization. This survey discusses these recent results in a very accessible fashion, and provides also a beautiful link between the study of fairness and classic probability theory.
I trust that you will enjoy reading this piece by Daniele and Hagen as much as I did. It is not often that one sees notions and results from several areas of mathematics and computer science combine so well to offer a formalization of a concept that confirms our intuition about it.
Fairness is an important concept that appears repeatedly in various forms in different areas of computer science, and plays a crucial role in the semantics and verification of reactive systems. Entire books are devoted to the notion of fairness---see, for instance, the monograph by Nissim Francez published in 1986---, and researchers in our community have painstakingly developed a taxonomy of various fairness properties that appear in the literature, such as unconditional fairness, weak fairness, strong fairness, and so on. This research is definitely important in light of the plethora of notions of fairness that have been proposed and studied in the literature.
But when is a temporal property expressing a fairness requirement? The authors of this column have recently developed a very satisfying answer to this fundamental question by offering three equivalent characterizations of ``fairness properties'' in the setting of linear-time temporal logic: a language-theoretic, a topological, and a game-theoretic characterization. This survey discusses these recent results in a very accessible fashion, and provides also a beautiful link between the study of fairness and classic probability theory.
I trust that you will enjoy reading this piece by Daniele and Hagen as much as I did. It is not often that one sees notions and results from several areas of mathematics and computer science combine so well to offer a formalization of a concept that confirms our intuition about it.
Tuesday, September 19, 2006
MacArthur Genius Awards for 2006
Lance Fortnow has a post on the latest batch of "genius awards" by the Mac Arthur foundation. Awards in disciplines of potential interest to the readers of this blog are to
Congratulations to the winners of the awards!
- Luis von Ahn.
- Terence Tao.
- Claire Tomlin. The announcement makes very interesting reading for a concurrency theorist, and for anyone interested in formal verification:
Much of Tomlin's research concentrates on aeronautical applications of hybrid systems research, particularly aircraft flight control and air traffic conflict resolution. As the number of variables increases and their interactions become more complex, it becomes ever more difficult to guarantee that systems will always be within safe limits. Tomlin has developed practical algorithms for determining when unsafe conditions may arise, and for establishing feedback control laws for a hybrid system guaranteed to remain within a safe subset of all reachable states.
Congratulations to the winners of the awards!
Jazz meets Process Algebra
Bas Luttik's band, the Residence Jazz Sextet, now has a web site, and a CD. I heard a demo version of the CD, and it sounds good. On the band's web site, you can also listen to mp3 demos of the tracks on the CD. Enjoy it!
Saturday, September 16, 2006
An Essay by Palamidessi and Valencia
Catuscia Palamidessi and Frank Valencia have written an essay on Languages for Concurrency, which will appear in the Programming Languages column of the Bulletin of the EATCS (edited by Ian Mackie (Kings College, London, UK) and David Sands (Göteborg, Sweden)). I enjoyed reading it myself---even though I hopefully knew the material it covers already---, and warmly recommend it.
This essay is a commendable example of `outreach activity´ from two very active members of the concurrency theory community. Let's give it to our students and colleagues from other areas of computer science to read, and let's try to sow the seeds of our research area in our departments. Something good is bound to come out of these kind of efforts. For the moment, thanks to Catuscia and Frank for offering a contribution in this direction.
This essay is a commendable example of `outreach activity´ from two very active members of the concurrency theory community. Let's give it to our students and colleagues from other areas of computer science to read, and let's try to sow the seeds of our research area in our departments. Something good is bound to come out of these kind of efforts. For the moment, thanks to Catuscia and Frank for offering a contribution in this direction.
Thursday, September 14, 2006
New Award to Moshe Vardi
Moshe Vardi has been named as a co-recipient of the first LICS-test-of-time award for his paper An Automata-Theoretic Approach to Automatic Program Verification, co-authored with Pierre Wolper. Congratulations to Moshe and Pierre for yet another award!
See http://www2.informatik.hu-berlin.de/lics/#awards for a description of the award. I think that the idea to look back 20 years for the award is a good one, and look forward to seeing more awards in areas of logic related to concurrency theory and formal verification.
See http://www2.informatik.hu-berlin.de/lics/#awards for a description of the award. I think that the idea to look back 20 years for the award is a good one, and look forward to seeing more awards in areas of logic related to concurrency theory and formal verification.
Experimental Blog for the IFIP WG on Concurrency Theory
Together with Wan Fokkink and Anna Ingolfsdottir, I recently set up a separate blog on concurrency theory. The aim of that blog is to serve as a dicussion forum for topics of interest to the members of IFIP WG1.8. I hope that the readers of this blog, if there are any, will contribute to the discussion threads that will be posted on the new blog.
Wednesday, September 06, 2006
PC Chair for FOSSACS 2008
FYI, the PC chair for FOSSACS 2008 will be Roberto Amadio. Sharpen your pencils and prepare good papers for that conference!
Tuesday, September 05, 2006
Gordon Plotkin is 60
On 7-8 September, LFCS, School of Informatics, University of Edinburgh, will host a symposium to celebrate Gordon Plotkin's 60th birthday. The detailed programme for that event lists a series of stellar speakers, and the list of participants is truly impressive.
This is really good to see. Gordon is one of the veritable giants in TCS, and he has had outstanding students and collaborators over the years. His contributions to the study of the semantics of programming languages (be it denotational, logical or operational) and to its mathematical underpinnings are well known, so I'll just limit myself to wishing Gordon a happy symposium.
This is really good to see. Gordon is one of the veritable giants in TCS, and he has had outstanding students and collaborators over the years. His contributions to the study of the semantics of programming languages (be it denotational, logical or operational) and to its mathematical underpinnings are well known, so I'll just limit myself to wishing Gordon a happy symposium.
Sunday, September 03, 2006
What Are the Most Important Open Problems in Concurrency?
Let us assume that one can assess the healthiness of a research field, say concurrency theory, by looking at the most important open problems in that field. These open problems can be used to try and convince researchers in another area and students that the field of concurrency theory is "alive and kicking", and maybe entice a few of them to work within the field.
Based upon this thought experiment, wouldn't it be a good thing to have a repository of open problems that identify the present state of development in concurrency theory, and suggest directions for further research?
At some point in the past, I started putting together a list of open problems, but I have not really maintained it for a while. Will you help me revive this enterprise by sending me, or posting as a comment to this blog entry, a description of your favourite open problems in concurrency theory, together with links to partial solutions and pointers to the literature? This input of yours might even form the basis for a useful installment of the Concurrency Column in the Bulletin of the EATCS, and generate a lot of research in our field following what Luca Trevisan has called in this very informative blog entry the "Hungarian approach to mathematics": pose very difficult problems, and let deep results, connections between different areas of math, and applications, come out as byproducts of the search for a solution.
By the way, Luca Trevisan has a few very interesting posts related to Szemeredi's theorem and other results in additive combinatorics. (See this one, and the five blog entries on Szemeredi's theorem.) Those posts give an inkling of the level of mathematical sophistication that has been reached in TCS research from the volume A camp. Check them out!
Based upon this thought experiment, wouldn't it be a good thing to have a repository of open problems that identify the present state of development in concurrency theory, and suggest directions for further research?
At some point in the past, I started putting together a list of open problems, but I have not really maintained it for a while. Will you help me revive this enterprise by sending me, or posting as a comment to this blog entry, a description of your favourite open problems in concurrency theory, together with links to partial solutions and pointers to the literature? This input of yours might even form the basis for a useful installment of the Concurrency Column in the Bulletin of the EATCS, and generate a lot of research in our field following what Luca Trevisan has called in this very informative blog entry the "Hungarian approach to mathematics": pose very difficult problems, and let deep results, connections between different areas of math, and applications, come out as byproducts of the search for a solution.
By the way, Luca Trevisan has a few very interesting posts related to Szemeredi's theorem and other results in additive combinatorics. (See this one, and the five blog entries on Szemeredi's theorem.) Those posts give an inkling of the level of mathematical sophistication that has been reached in TCS research from the volume A camp. Check them out!
Thursday, August 31, 2006
A New Yorker Article on the Poincaré Conjecture
Yesterday I finished reading a rather long, but interesting article published in the New Yorker. The article, written by Sylvia Nasar (of Beautiful Mind fame) and David Gruber, describes some of the developments surrounding the proof of the Poincaré conjecture, has excerpts of an interview with Perelman, and offers us a glimpse of what happens behind the scenes of the mathematical arena. The former Fields medal winner and top-notch mathematician Shing-Tung Yau appears as the "villain" in the story.
I do not know if the content of the article is truly trustworthy, but it makes for some interesting, and at times arresting, reading. This excerpt, for one, tells the remarkable story of the recent publication of what could be a key paper in the story of the solution of the Poincaré conjecture:
On April 13th of this year, the thirty-one mathematicians on the editorial board of the Asian Journal of Mathematics received a brief e-mail from Yau and the journal’s co-editor informing them that they had three days to comment on a paper by Xi-Ping Zhu and Huai-Dong Cao titled “The Hamilton-Perelman Theory of Ricci Flow: The Poincaré and Geometrization Conjectures,” which Yau planned to publish in the journal. The e-mail did not include a copy of the paper, reports from referees, or an abstract. At least one board member asked to see the paper but was told that it was not available. On April 16th, Cao received a message from Yau telling him that the paper had been accepted by the A.J.M., and an abstract was posted on the journal’s Web site.
Quite a remarkable refereeing process for a paper proving one of the Millennium Problems of the Clay mathematical institute!
I do not know if the content of the article is truly trustworthy, but it makes for some interesting, and at times arresting, reading. This excerpt, for one, tells the remarkable story of the recent publication of what could be a key paper in the story of the solution of the Poincaré conjecture:
On April 13th of this year, the thirty-one mathematicians on the editorial board of the Asian Journal of Mathematics received a brief e-mail from Yau and the journal’s co-editor informing them that they had three days to comment on a paper by Xi-Ping Zhu and Huai-Dong Cao titled “The Hamilton-Perelman Theory of Ricci Flow: The Poincaré and Geometrization Conjectures,” which Yau planned to publish in the journal. The e-mail did not include a copy of the paper, reports from referees, or an abstract. At least one board member asked to see the paper but was told that it was not available. On April 16th, Cao received a message from Yau telling him that the paper had been accepted by the A.J.M., and an abstract was posted on the journal’s Web site.
Quite a remarkable refereeing process for a paper proving one of the Millennium Problems of the Clay mathematical institute!
Saturday, August 26, 2006
Italian TCS Presence at the ICM 2006
Today was a good day for Italian TCS at the International Congress of Mathematicians 2006. The inaugural talk in the section on Mathematical Aspects of Computer Science was delivered by Luca Trevisan (UC Berkeley). Luca's talk was based on the paper Pseudorandomness and Combinatorial Constructions.
Congratulations to Luca for being invited to deliver a talk at ICM 2006.
Question: How many Italian computer scientists have been invited speakers at the section on Mathematical Aspects of CS at the ICM so far?
I do not know the answer myself. Does any of my readers do?
Congratulations to Luca for being invited to deliver a talk at ICM 2006.
Question: How many Italian computer scientists have been invited speakers at the section on Mathematical Aspects of CS at the ICM so far?
I do not know the answer myself. Does any of my readers do?
Subscribe to:
Posts (Atom)