It is a humbling experience to see young stars in our research world shine very brightly and very fast.
Yesterday, while reading the comments to this post by Lance Fortnow, I learned that Mihai Pătraşcu, the author of three accepted papers at FOCS 2006, is a first-year graduate student, and submitted the papers when he was still an undergraduate at MIT! He was also the co-recipient of the best Best Student ICALP Paper for 2005.
Earlier this year, Jacob Fox (MIT) won the Frank and Brennie Morgan Prize for Outstanding Research in Mathematics by an Undergraduate Student. (See this link.) The prize citation mentions that:
Jacob Fox’s research exhibits a formidable ability to get to the heart of the issues in the problems at hand, and the ability to develop extremely ingenious and novel techniques. In addition to being able to solve problems posed by others, Fox has also excelled at finding topics all by himself, formulating novel conjectures and approaches to solutions. His accomplishments are shaping his areas of research, and are of extraordinary promise for the future.
If you want to read about one of the things he has done, look here. (Make sure you don't miss Dana Scott's feedback to that post!)
I am always overawed by these accomplishments from young researchers, and wish both Mihai and Jacob the best of luck in fulfilling their exceptional promise. However, no matter how gifted they are, it is a fair bet that this won't be easy. They will have to show a lot of appetite for hard work and guts in doing so. Keep it up guys!
Before closing, and in Football World Cup spirit, let me suggest that you have a look at this short movie by Marcus du Sautoy, professor of mathematics at Oxford University, where he uses football to explain the proof of Euclid's theorem to the effect that there are infinitely many prime numbers. Marcus du Sautoy is the author of the excellent book The Music of the Primes. Check it out, if you have not read it already.
Thursday, June 29, 2006
Wednesday, June 28, 2006
FOCS 2006 Accepted Papers
The list of accepted papers for FOCS 2006 (47th Annual Symposium on Foundations of Computer Science) is now available. A brief look at the list seems to indicate the absence of "Volume B" papers. I do not know whether this is due to the lack of submissions to that conference from "Volume B" researchers, but I find it sad that a very prestigious conference with that name has no papers on, for instance, applications of logic to CS.
I am glad to see that there is a paper co-authored by BRICS colleagues of mine, namely
Improved Dynamic Planar Point Location
by Lars Arge and Gerth Stolting Brodal and Loukas Georgiadis
Congratulations to Lars and Gerth!
I am glad to see that there is a paper co-authored by BRICS colleagues of mine, namely
Improved Dynamic Planar Point Location
by Lars Arge and Gerth Stolting Brodal and Loukas Georgiadis
Congratulations to Lars and Gerth!
Monday, June 26, 2006
An Eight Page Paper of Kleene
In his article Stephen Cole Kleene - a reminescence, Saunders Mac Lane quotes a letter from Kleene to his mother. In that letter, Kleene wrote:
"Rosser and my article is deadly. It is only 8 pages typed....,but it would require reading a couple of hundred pages perhaps to make full check up on it all. One sentence takes 10 pages to prove."
Alas, the piece does not say what paper of Kleene's the letter refers to. However, no matter what paper it was, I do not believe that that type of distillation is ever useful when writing a paper. Who could claim to understand those 8 pages after all?
Addendum: One of my readers pointed out that the essay does point out the title of the paper. It is
Kleene, S. C.; Rosser, J. B.
The inconsistency of certain formal logics.
Ann. of Math. (2) 36 (1935), no. 3, 630--636.
The paper is available online from: http://www.jstor.org/view/0003486x/di961655/96p00874/0.
Thanks to the anonymous reader, and shame on me for not checking my sources as thoroughly as I should have done, and trusting my untrustworthy memory.
"Rosser and my article is deadly. It is only 8 pages typed....,but it would require reading a couple of hundred pages perhaps to make full check up on it all. One sentence takes 10 pages to prove."
Alas, the piece does not say what paper of Kleene's the letter refers to. However, no matter what paper it was, I do not believe that that type of distillation is ever useful when writing a paper. Who could claim to understand those 8 pages after all?
Addendum: One of my readers pointed out that the essay does point out the title of the paper. It is
Kleene, S. C.; Rosser, J. B.
The inconsistency of certain formal logics.
Ann. of Math. (2) 36 (1935), no. 3, 630--636.
The paper is available online from: http://www.jstor.org/view/0003486x/di961655/96p00874/0.
Thanks to the anonymous reader, and shame on me for not checking my sources as thoroughly as I should have done, and trusting my untrustworthy memory.
Sunday, June 25, 2006
Goal: To Be Amongst the Top 100 Best Universities
On Thursday, 31 May, Magnús Halldórsson invited some of the participants at our second ICE-TCS theory day for a barbeque at his house. This was a very pleasant evening, and a fitting end to a very satisfying day from both a social and a scientific point of view.
During the course of the evening, Moshe Vardi regaled us with some of his interesting opinions on all kinds of academic issues, some of which he has aired in a very stimulating SIGMOD RECORD interview. (See Moshe Vardi Speaks Out (on the Proof, the Whole Proof, and Nothing But the Proof) by Marianne Winslett. SIGMOD RECORD, Volume 35, Number 1, March 2006. Do read it!)
One of the things Moshe said was that the goal of improving a department's/university's ranking in one of the many rankings of academic institutions that are available today is not a realistic one. One should focus on measurable goals that one has some form of control over---for instance, increasing the number/quality of graduate students, or the number of papers published by members of staff in, say, I&C and TCS, or whatever else is deemed to lead to a measurable improvement in the institution. Moshe says in that interview that he never felt that the goal of ranking improvement was attainable or useful.
While hearing him air these opinions, I was reminded of the recent pronouncement by the rector of the University of Iceland, who said that by 2010 that university should be ranked amongst the top 100 in the world. This is a very tall order, and I believe that it is not achievable with the economic and human resources that are available for that institution, or any other university in Iceland for what matters.
What might turn out to be useful in setting the university such a lofty goal is the process of change in its daily academic life that this will entail. To be a top 100 university, the percentage of "research active" members of staff will have to increase considerably, the quality of the publication outlets of most members of staff will have to improve, and there will have to be a push towards research that is recognized internationally. Publishing scientific articles in Icelandic in the single Icelandic scientific journal won't be enough for getting tenure or promotion.
However, setting an unachievable goal may also have a negative psychological repercussion. What will the reaction of the staff members be when they will double, say, their scientific output both in quality and quantity, and then discover that their university is still not ranked amongst the top 500 in the world, let alone amongst the top 100? I would not be amused myself. Worse still, people might feel that their efforts have been in vain, and get back to the old, cosy mould.
University administrators, like army generals or chiefs of staff, should also think about the morale of their troops, who are, after all, those who do battle in the classroom and in the scientific arena on a daily basis.
During the course of the evening, Moshe Vardi regaled us with some of his interesting opinions on all kinds of academic issues, some of which he has aired in a very stimulating SIGMOD RECORD interview. (See Moshe Vardi Speaks Out (on the Proof, the Whole Proof, and Nothing But the Proof) by Marianne Winslett. SIGMOD RECORD, Volume 35, Number 1, March 2006. Do read it!)
One of the things Moshe said was that the goal of improving a department's/university's ranking in one of the many rankings of academic institutions that are available today is not a realistic one. One should focus on measurable goals that one has some form of control over---for instance, increasing the number/quality of graduate students, or the number of papers published by members of staff in, say, I&C and TCS, or whatever else is deemed to lead to a measurable improvement in the institution. Moshe says in that interview that he never felt that the goal of ranking improvement was attainable or useful.
While hearing him air these opinions, I was reminded of the recent pronouncement by the rector of the University of Iceland, who said that by 2010 that university should be ranked amongst the top 100 in the world. This is a very tall order, and I believe that it is not achievable with the economic and human resources that are available for that institution, or any other university in Iceland for what matters.
What might turn out to be useful in setting the university such a lofty goal is the process of change in its daily academic life that this will entail. To be a top 100 university, the percentage of "research active" members of staff will have to increase considerably, the quality of the publication outlets of most members of staff will have to improve, and there will have to be a push towards research that is recognized internationally. Publishing scientific articles in Icelandic in the single Icelandic scientific journal won't be enough for getting tenure or promotion.
However, setting an unachievable goal may also have a negative psychological repercussion. What will the reaction of the staff members be when they will double, say, their scientific output both in quality and quantity, and then discover that their university is still not ranked amongst the top 500 in the world, let alone amongst the top 100? I would not be amused myself. Worse still, people might feel that their efforts have been in vain, and get back to the old, cosy mould.
University administrators, like army generals or chiefs of staff, should also think about the morale of their troops, who are, after all, those who do battle in the classroom and in the scientific arena on a daily basis.
Saturday, June 24, 2006
NWPT'06 in Reykjavík
Yesterday Anna and I sent the preliminary announcement for the Nordic Workshop on Programming Theory 2006 that we'll organize at Reykjavík University to several mailing lists. Most likely if you are reading this post, you will receive one or more of our announcements. Still I cannot resist advertising the event using this medium.
The NWPT'06 workshop will take place in the period 18-20 October. This is the 18th installment of this event, which is a forum bringing together programming theorists from the Nordic and Baltic countries (but also elsewhere), and the first time that the workshop will be held in Iceland.
The scope for the workshop mentions several topics of interest to concurrency theorists, and the list of invited speakers includes Gerd Behrmann, Matthew Hennessy, Hanne Riis Nielson, and David Sands.
The NWPT'06 workshop will take place in the period 18-20 October. This is the 18th installment of this event, which is a forum bringing together programming theorists from the Nordic and Baltic countries (but also elsewhere), and the first time that the workshop will be held in Iceland.
The scope for the workshop mentions several topics of interest to concurrency theorists, and the list of invited speakers includes Gerd Behrmann, Matthew Hennessy, Hanne Riis Nielson, and David Sands.
If you wish to give a talk at the workshop, all you have to do is to submit an abstract of 1-3 pages (ps or pdf, printable on A4 paper) to nwpt06(at)ru(dot)is by the 19th September 2006. Submission of work submitted for formal publication elsewhere and work in progress is permitted.
The abstracts of the accepted contributions will be available at the workshop. After the workshop, selected papers will be published in a special issue of Nordic Journal of Computing.
Why don't you use this opportunity to visit Iceland?
Wednesday, June 21, 2006
Two-Body Problem
Last Monday's post in Lance Fortnow's excellent blog addressed the two-body problem. This is the problem that academic couples have to solve in finding (academic) jobs in the same city. It is not an uncommon problem at all in Computer Science, and sometimes departments/universities showing a willingness to help solve instances of this problem greatly improve the quality of their academic staff in the process. For instance, Kári Ragnarsson (a member of my extended family and a blossoming algebraic topologist who has a two-body problem himself) tells me that the Department of Mathematical Sciences at the University of Aberdeen has benefited by solving two instances of the two-body problem. Lance Fortnow himself hints at the solution of two-body problems as being one of the factors in the rise of the theory group at Georgia Tech.
One of the readers of Lance's blog points out that:
In Germany the two body problem is so bad that many academic couples have resigned themselves to living apart and commuting back and forth on the weekends.
The situation described in the last comment is not limited to Germany. My understanding is that the same applies in Italy too. The two-body problem becomes even more difficult in Italy when one of the academics involved is not Italian. I know personally of at least two instances of the two-body problem involving one Italian and one non-Italian that could be solved abroad (twice and in two different countries in both cases), but apparently not in Italy. No doubt there are many more examples.
As with all problems of this type, there are no silver bullets to a solution. One has to try and work things out in the best possible way, without sacrificing one's family life too much---assuming that having a family life is a priority for the people involved, of course. (And this is even harder when there are children involved.) However, I find it surprising that institutions/universities that do not have such a high standing are not willing to take the plunge and help scientists solve two-body problems that would improve their quality. My message to the heads of department of those institutions would be that being creative in this and other situations might make it possible for them to attract excellent academic staff members that would normally not even consider applying for a job at their institutions.
Post Scriptum: Above I wrote that two body-problems are not uncommom. I already mentioned Kári and his girlfriend (algebraic topology marries combinatorics). Two of my very best collaborators (Wan Fokkink and Bas Luttik) also live with computer science researchers (Judi Romijn and Simona Orzan, respectively). Of course, I should not forget couples like Dale Miller and Catuscia Palamidessi, or Orna and Raz Kupferman. This is only the tip of the iceberg, I believe, and somewhere inside that iceberg one can also find Anna and me.
One of the readers of Lance's blog points out that:
In Germany the two body problem is so bad that many academic couples have resigned themselves to living apart and commuting back and forth on the weekends.
The situation described in the last comment is not limited to Germany. My understanding is that the same applies in Italy too. The two-body problem becomes even more difficult in Italy when one of the academics involved is not Italian. I know personally of at least two instances of the two-body problem involving one Italian and one non-Italian that could be solved abroad (twice and in two different countries in both cases), but apparently not in Italy. No doubt there are many more examples.
As with all problems of this type, there are no silver bullets to a solution. One has to try and work things out in the best possible way, without sacrificing one's family life too much---assuming that having a family life is a priority for the people involved, of course. (And this is even harder when there are children involved.) However, I find it surprising that institutions/universities that do not have such a high standing are not willing to take the plunge and help scientists solve two-body problems that would improve their quality. My message to the heads of department of those institutions would be that being creative in this and other situations might make it possible for them to attract excellent academic staff members that would normally not even consider applying for a job at their institutions.
Post Scriptum: Above I wrote that two body-problems are not uncommom. I already mentioned Kári and his girlfriend (algebraic topology marries combinatorics). Two of my very best collaborators (Wan Fokkink and Bas Luttik) also live with computer science researchers (Judi Romijn and Simona Orzan, respectively). Of course, I should not forget couples like Dale Miller and Catuscia Palamidessi, or Orna and Raz Kupferman. This is only the tip of the iceberg, I believe, and somewhere inside that iceberg one can also find Anna and me.
Tuesday, June 20, 2006
Finite Basis for CCS
After a long sabbatical from conference submission (at least by the standards of present day Computer Science), I have two papers accepted at ICALP'06 in Venice. I have already reported on one of them on this diary. The other paper, entitled A Finite Equational Base for CCS with Left Merge and Communication Merge is joint work with Wan Fokkink, Anna Ingólfsdóttir and Bas Luttik, and the full version is available as a BRICS report. In that paper, we provide a complete equational axiomatization of bisimulation equivalence over the relabelling-, restriction- and recursion-free fragment of CCS, enriched with the left and communication merge operators proposed by Jan Bergstra and Jan Willem Klop. The axiomatization is complete in the sense of classic universal algebra---that is, it can prove all of the valid equations, whose terms may contain variables---and consists mostly of standard equations that had been considered in previous related work. The proof strategy is also based on the classic approach based on normal forms. However, the devil and the pudding are in the details that need to be worked out in order to make the general proof strategy "work" in the specific setting. A lot of care needs to be taken in defining a suitable notion of distinguishing substitution, and in proving that our hunches do work.
I find this result satisfying, and look forward to hearing Bas's ICALP talk based on it. Once again, thanks a lot to my co-authors for a very pleasant and instructive collaboration.
I find this result satisfying, and look forward to hearing Bas's ICALP talk based on it. Once again, thanks a lot to my co-authors for a very pleasant and instructive collaboration.
Saturday, June 17, 2006
H is the Magic Number
Humans seem to like metrics of all sorts, and we tend to develop and apply them also to subjects that do not naturally lend themselves to "objective measurement". George David Birkhoff wrote a book entitled Aesthetic Measure (1933) to develop a mathematical theory capable of measuring the aesthetic value of a piece of art. (See this nice little article to get an idea of the gist of Birkhoff's proposal.)
In our age in which "impact" and "leadership" are two of the main gods of academia, we are trying to do the G.D. Birkhoff and develop all kinds of metrics to determine how valuable our research is. The discussion of whether these metrics are any good at all, and whether they should be used in evaluating applicants for positions/promotion etc., would need a series of posts. Here I just want to point out one of these metrics.
Jorge Hirsch developed the h-number as a measure of the scientific output of a researcher. Being curious, many of us, including yours truly, will immediately try to determine (an approximation to) their h-number. This is now easy to do, thanks to a a script written by my BRICS colleague Michael I. Schwartzbach (University of Aarhus), which consults Google Scholar. Here is Michael's web interface.
According to Michael's script, my h-number is something like 14. This is far off from the h-number of people among the h-number elite maintained by Jens Palsberg (UCLA), but then again anything else would have been a major surprise to me.
Enjoy computing your h-number and those of your friends/competitors, but please resist the temptation of reading too much into this or any other metric.
[In case you are wondering where the title of this post comes from, I can tell you that it is based on the title of the second song in 3 Feet High and Rising, the debut album from American hip-hop trio De La Soul. In that song, "the magic number" was, guess what, three.]
In our age in which "impact" and "leadership" are two of the main gods of academia, we are trying to do the G.D. Birkhoff and develop all kinds of metrics to determine how valuable our research is. The discussion of whether these metrics are any good at all, and whether they should be used in evaluating applicants for positions/promotion etc., would need a series of posts. Here I just want to point out one of these metrics.
Jorge Hirsch developed the h-number as a measure of the scientific output of a researcher. Being curious, many of us, including yours truly, will immediately try to determine (an approximation to) their h-number. This is now easy to do, thanks to a a script written by my BRICS colleague Michael I. Schwartzbach (University of Aarhus), which consults Google Scholar. Here is Michael's web interface.
According to Michael's script, my h-number is something like 14. This is far off from the h-number of people among the h-number elite maintained by Jens Palsberg (UCLA), but then again anything else would have been a major surprise to me.
Enjoy computing your h-number and those of your friends/competitors, but please resist the temptation of reading too much into this or any other metric.
[In case you are wondering where the title of this post comes from, I can tell you that it is based on the title of the second song in 3 Feet High and Rising, the debut album from American hip-hop trio De La Soul. In that song, "the magic number" was, guess what, three.]
Tuesday, June 13, 2006
Reacting to Rejections
The Combinatorics group affiliated with ICE-TCS is presently hosting the conference on Permutation Patterns 2006. The talks at that conference quickly become way too hard for me to understand, but I'll make a point of attending one or two talks every day since this involves running up and down a few flights of stairs from my office. Maybe I am easily impressed, but the formulae these people come up with in order to count the number of structures having certain properties are just incredible. They seem to come out of the hat of a magician.
What does this conference have to do with the title of this post, you may ask? Well, the second talk I attended yesterday was delivered by Mireille Bousquet-Mélou, who presented the paper Forest-Like Permutations (joint work with Steven Butler). This paper is mentioned in Doron Zeilberger's Opinon 72 that I just read, where it is compared with Enumeration Schemes for Restricted Permutations by Vince Vatter. In that post, Doron Zeilberger makes the following points:
Unfortunately, many human mathematicians still don't realize the importance of this activity, and dismiss it as "just a computer program" and "no new mathematics". These were the reasons given to the rejection (by Journal of Combinatorial Theory-Series A) of my recent paper Automatic CounTilings. It is true, that in some sese it has "no new math", but it has something far more important, it has New META-MATH. It is an example of a methodology that will make all computer-free math obsolete very soon. I am not so paranoid to claim that the editors (that include enumeration guru Mireille Bousquet-Melou) deliberately rejected the paper because, being practicioners of traditional math, they are afraid to be put out of business. They are not so devious. They simply are so wrapped-up in their own way of doing things that from their perspective they "don't see the point".
On the web page for the "rejected paper", Zeilberger writes:
Added April 14, 2006: This article was submitted to Journal of Combinatorial Theory Series A, and was stupidly rejected by its Managing Editor, Helene Barcelo, and the members of its Advisory Board, that includes, surprisingly and sadly, Tiling expert Mireille Bousquet-Melou. Read the Narrow-Minded and Ignorant Referee's Report and my response .
Luckily, nowadays, publishing in a "real" journal is really only a formality, and this masterpiece is hence published in this Personal Journal.
Most of us get more or less upset when our papers are rejected from a conference/journal, but I have never seen before someone write to the editor-in-chief saying that
What does this conference have to do with the title of this post, you may ask? Well, the second talk I attended yesterday was delivered by Mireille Bousquet-Mélou, who presented the paper Forest-Like Permutations (joint work with Steven Butler). This paper is mentioned in Doron Zeilberger's Opinon 72 that I just read, where it is compared with Enumeration Schemes for Restricted Permutations by Vince Vatter. In that post, Doron Zeilberger makes the following points:
- computer-generated mathematics is the future, whilst human-generated mathematics is the past;
- many human mathematicians still don't realize the importance of this activity, and dismiss it as "just a computer program" and "no new mathematics".
Unfortunately, many human mathematicians still don't realize the importance of this activity, and dismiss it as "just a computer program" and "no new mathematics". These were the reasons given to the rejection (by Journal of Combinatorial Theory-Series A) of my recent paper Automatic CounTilings. It is true, that in some sese it has "no new math", but it has something far more important, it has New META-MATH. It is an example of a methodology that will make all computer-free math obsolete very soon. I am not so paranoid to claim that the editors (that include enumeration guru Mireille Bousquet-Melou) deliberately rejected the paper because, being practicioners of traditional math, they are afraid to be put out of business. They are not so devious. They simply are so wrapped-up in their own way of doing things that from their perspective they "don't see the point".
On the web page for the "rejected paper", Zeilberger writes:
Added April 14, 2006: This article was submitted to Journal of Combinatorial Theory Series A, and was stupidly rejected by its Managing Editor, Helene Barcelo, and the members of its Advisory Board, that includes, surprisingly and sadly, Tiling expert Mireille Bousquet-Melou. Read the Narrow-Minded and Ignorant Referee's Report and my response .
Luckily, nowadays, publishing in a "real" journal is really only a formality, and this masterpiece is hence published in this Personal Journal.
Most of us get more or less upset when our papers are rejected from a conference/journal, but I have never seen before someone write to the editor-in-chief saying that
>In conclusion, although a good paper of this kind would be interesting,As usual, Doron Zeilberger seems to be ahead of the pack here, and I expect that similar types of public reactions to referee reports/rejections will become more common. However, we should all bear in mind that, as they say in Naples, "Even the coakroach is beautiful for its mum!" We are probably not so well equipped to judge our own "masterpieces" critically.
>I dont believe that the present manuscript meets the required standards for
>acceptance in the Journal.
You are right here. It is way too good for it! I kick myself for being nice and
submitting this paper to your narrow-minded pretentious journal!
It won't happen again.
Saturday, June 10, 2006
The Importance of Mathematics
Timothy Gowers (Fields medal winner for 1998) is a mathematician who seems to have the gift of being able to explain his subject matter even to a layman like me. His book "Mathematics: A Very Short Introduction" is a real gem, and so is the public lecture entitled "The Importance of Mathematics" that he delivered at the Clay Millenium meeting. The video of this lecture is available from http://claymath.msri.org/gowers2000.mov. A transcript of the talk is at http://www.dpmms.cam.ac.uk/~wtg10/importance.pdf. It is one of those pieces that I read every now and then, and that brims with wit and little pearls of scientific wisdom. If you wish to convince somebody of the importance of theoretical research, then you could do worse than to borrow some of his arguments.
Here is a sample quote:
"However, if one has a bright idea, it is important to sit down and check the details thoroughly. If my own experience is anything to go by, the great majority of bright ideas are either wrong, or have been had by hundreds of people before."
If my experience is anything to go by, reading this essay will give you a few intellectually pleasing moments.
Thursday, June 08, 2006
Poincaré Conjecture
The American Mathematical Society has posted a news item on two key papers on the Poincaré Conjecture. The posting reads:
Within the past two weeks two papers have been issued on proofs of the Poincaré Conjecture: "A Complete Proof of the Poincaré and Geometrization Conjectures--Application of the Hamilton-Perelman Theory of the Ricci Flow," by Huai-Dong Cao and Xi-Ping Zhu (Asian Journal of Mathematics, June 2006) and "Notes on Perelman's Papers," by Bruce Kleiner and John Lott (on ArXiv, May 25, 2006).
The first of these two papers, which is roughly 300 pages long, is published in an archival journal, but not one that a mathematician would consider to be top-notch. This is odd, considering the importance and the financial worth of the result. If that paper is correct, who will receive the 1 million dollars from the Clay Mathematical Institute? To whom should the credit for the result go? Perelman or the Chinese mathematicians? And will Perelman receive the Fields medal at ICM 2006? I believe that there will be interesting developments in this story.
For the record, here is a quote from the recent 192 page preprint of Kleiner and Lott: "Regarding the proofs, [Perelman's papers] contain some incorrect statements and incomplete arguments, which we have attempted to point out to the reader... We did not find any serious problems, meaning problems that cannot be corrected by using the methods introduced by Perelman."
Within the past two weeks two papers have been issued on proofs of the Poincaré Conjecture: "A Complete Proof of the Poincaré and Geometrization Conjectures--Application of the Hamilton-Perelman Theory of the Ricci Flow," by Huai-Dong Cao and Xi-Ping Zhu (Asian Journal of Mathematics, June 2006) and "Notes on Perelman's Papers," by Bruce Kleiner and John Lott (on ArXiv, May 25, 2006).
The first of these two papers, which is roughly 300 pages long, is published in an archival journal, but not one that a mathematician would consider to be top-notch. This is odd, considering the importance and the financial worth of the result. If that paper is correct, who will receive the 1 million dollars from the Clay Mathematical Institute? To whom should the credit for the result go? Perelman or the Chinese mathematicians? And will Perelman receive the Fields medal at ICM 2006? I believe that there will be interesting developments in this story.
For the record, here is a quote from the recent 192 page preprint of Kleiner and Lott: "Regarding the proofs, [Perelman's papers] contain some incorrect statements and incomplete arguments, which we have attempted to point out to the reader... We did not find any serious problems, meaning problems that cannot be corrected by using the methods introduced by Perelman."
Wednesday, June 07, 2006
Brane Calculi in Reykjavík
Yesterday, Nadia Busi (University of Bologna) delivered a seminar entitled Expressiveness Issues in Bio-Inspired Calculi at ICE-TCS@Reykjavík University. The seminar presented results pertaining to the Turing-completeness of variants on Brane Calculi - a family of process calculi based on a set of biologically inspired primitives for modeling the interactions of dynamically nested membranes that have been recently proposed by Luca Cardelli. Two basic Brane Calculi have been proposed: the Phago/Exo/Pino (PEP) calculus, inspired by the biological operations of endocytosis and exocytosis, and the Mate/Bud/Drip (MBD) calculus, inspired by membrane fusion and fission. Nadia presented some interesting results on the comparison of the expressiveness of the PEP and the MBD calculi, as well as of their deterministic fragments, with respect to their ability to perform computations. The talk generated some interest amongst the participants, including some of our own MSc students.
Nadia's talk inaugurated a new seminar series under the auspices of ICE-TCS. This series aims at highlighting the achievements of women in TCS, and will hopefully help us convince some of the bright, local, female students that TCS is a subject for them.
Only time will tell whether this will work.
Nadia's talk inaugurated a new seminar series under the auspices of ICE-TCS. This series aims at highlighting the achievements of women in TCS, and will hopefully help us convince some of the bright, local, female students that TCS is a subject for them.
Only time will tell whether this will work.
Monday, June 05, 2006
Do We Really "Choose" A Research Area?
Last Friday, Anna and I were driving Wan Fokkink and Moshe Vardi to the Blue Lagoon. During the trip, Moshe asked us how we ended up choosing the areas of research we work in. His tenet, if I recall it correctly, was that serendipity and the influence of the people we meet at crucial points in our career are decisive, and we really do not choose consciously an area per se.
It turns out that the person who triggered Moshe's research interests in databases, the area of research he started his career in, was Catriel Beeri, who taught a course at the Weizmann Institute as a guest lecturer when Moshe was a student there. One of the papers that Beeri gave his students to read contained the statement of an open problem that Moshe worked on and solved. The rest is history. Moshe's collaboration with Pierre Wolper was instead triggered by the decision that they would share a room at a conference in order to save money. This led to the research that won them the Gödel Prize 2000 and the Paris Kannellakis Award for 2005!
Wan holds an MSc in Mathematics, but, despite liking the subject very much, he found research in that field "a lonely affair." He was about to go out and work in industry when a PhD position in Computer Science became available in Jan Bergstra's group. Chris Verhoef, who had studied mathematics with Wan's brother, suggested that Wan would apply for that position, and Jan Bergstra was obviously very convincing during the interview :-)
Anna also holds an MSc. in Mathematics, but she had to take a minor in a related subject. The subject was Computer Science and her project supervisor was a young and very keen Kim G. Larsen. Kim's supervision was so inspirational that Anna switched to Computer Science, and worked out a characteristic formula construction for bisimulation equivalence over finite LTSs together with two fellow students.
As for me, I heard Ugo Montanari mention during a course I liked a lot that "The semantics of concurrency was a difficult and active area of research." Without any specific reason, I decided that that would be the topic of my MSc. thesis. This turned out to become reality when I met Rocco De Nicola, who had just come back to Pisa after finishing his PhD thesis at Edinburgh under the supervision of Matthew Hennessy. Matthew and Rocco eventually became my mentors.
I would not be surprised if many of my readers have a similar story to tell. The people we meet and learn from do shape our interests and our attitude to life in research. That's one of the reasons why we should give a good example to young researchers.
It turns out that the person who triggered Moshe's research interests in databases, the area of research he started his career in, was Catriel Beeri, who taught a course at the Weizmann Institute as a guest lecturer when Moshe was a student there. One of the papers that Beeri gave his students to read contained the statement of an open problem that Moshe worked on and solved. The rest is history. Moshe's collaboration with Pierre Wolper was instead triggered by the decision that they would share a room at a conference in order to save money. This led to the research that won them the Gödel Prize 2000 and the Paris Kannellakis Award for 2005!
Wan holds an MSc in Mathematics, but, despite liking the subject very much, he found research in that field "a lonely affair." He was about to go out and work in industry when a PhD position in Computer Science became available in Jan Bergstra's group. Chris Verhoef, who had studied mathematics with Wan's brother, suggested that Wan would apply for that position, and Jan Bergstra was obviously very convincing during the interview :-)
Anna also holds an MSc. in Mathematics, but she had to take a minor in a related subject. The subject was Computer Science and her project supervisor was a young and very keen Kim G. Larsen. Kim's supervision was so inspirational that Anna switched to Computer Science, and worked out a characteristic formula construction for bisimulation equivalence over finite LTSs together with two fellow students.
As for me, I heard Ugo Montanari mention during a course I liked a lot that "The semantics of concurrency was a difficult and active area of research." Without any specific reason, I decided that that would be the topic of my MSc. thesis. This turned out to become reality when I met Rocco De Nicola, who had just come back to Pisa after finishing his PhD thesis at Edinburgh under the supervision of Matthew Hennessy. Matthew and Rocco eventually became my mentors.
I would not be surprised if many of my readers have a similar story to tell. The people we meet and learn from do shape our interests and our attitude to life in research. That's one of the reasons why we should give a good example to young researchers.
Sunday, June 04, 2006
Second ICE-TCS Symposium
Last Wednesday, 31 May, ICE-TCS organized its second one-day symposium. The aim of these "theory days" is to give the Icelandic computer science community a bird's eye view of the area of Theoretical Computer Science, with emphasis on the research fields of the members of the centre.
The second symposium was graced by the presence of three outstanding keynote speakers from outside Iceland, namely Wan Fokkink, Jan Kratochvil and Moshe Vardi. The presentations by the invited speakers were complemented by 25 minute talks delivered by Ragnar K. Karlsson, Magnús M. Halldórsson, Anders Claesson/Sergey Kitaev (who shared the closing slot) and myself.
The morning session was devoted to "Volume B" talks. Moshe gave the meeting the best of starts with a talk describing the design of the ForSpec Temporal Logic (FTL), the new temporal logic of ForSpec, Intel's new formal property-specification language, which is today part of Synopsis OpenVera hardware verification language. The focus of Moshe's talk was on design rationale, rather than a detailed language description, and during the presentation he offered a very accessible discussion of the field of model checking, of linear and branching time temporal logics, and of the automata-theoretic approach to LTL model checking. Moshe also told the audience that his analysis of the relative merits of LTL and CTL has been referred to as "character assassination" by some of our colleagues :-)
Moshe's talk was immediately followed by the second keynote address, which was delivered by Wan Fokkink. Wan's talk presented joint work with Bard Bloom, Rob van Glabbeek and Paulien de Wind devoted to the systematic derivation of congruence formats for various behavioural equivalences in the linear-time/branching-time spectrum from decomposition results for the modal logics that characterize them.
I closed the morning session with a talk presenting joint work with Taolue Chen, Wan Fokkink and Anna Ingólfsdóttir on the axiomatizability of bisimulation equivalence over the language BCCSP extended with the priority operator.
The afternoon session was devoted to "Volume A" talks. The first talk in that session was delivered by Jan Kratochvil, who presented a survey of work on graph homomorphisms, viz. edge-preserving vertex mappings between two graphs. He showed how the use of graph homomorphisms unifies previously defined and independently studied notions such as graph covers, role assignments, and distance constrained graph labelings. Jan surveyed recent results and open problems related to these notions, with special emphasis on the computational complexity issues. He also mentoned connections to the Constraint Satisfaction Problem and the Dichotomy Conjecture.
Graphs featured also in the two 25 minute talks that followed Jan's address. The first talk was delivered by Ragnar Karlsson, who had defended his MSc thesis the day before. (For the record, Ragnar is the first MSc student to graduate under the suprvision of a member of ICE-TCS, viz. Magnús M. Halldórsson. Congratulations, Ragnar!) Ragnar presented the main results in his MSc thesis related to so-called strip graphs. These graphs are formed by an interval graph together with an equivalence relation on the vertices, and can be used to model the classic Job Interval Selection Problem (JISP) on one machine. In this problem, the input is a set of jobs, each of which is a set of intervals, and the object is to select at most one interval from each job such that no two chosen intervals intersect. This corresponds to being given multiple possible run-times for each job and trying to schedule as many jobs as possible. This problem is known to be NP-complete. However, strip graphs provide a very nice way to model the input of this graph and, by using structural observations of the input, Ragnar was able to find a fairly efficient exponential algorithm to solve this problem.
Magnús M. Halldórsson presented the next 25 minute talk, reporting on joint work with Takeshi Tokuyama and Alexander Wolff. The scientific director of ICE-TCS considered the problem of computing a non-crossing spanning tree of a graph that has been embedded in the plane. This problem is known to be NP-hard. During his talk, Magnús considered the complexity of the problem in terms of an input parameter k: the number of pairs of edges that cross. He gave an algorithm with a dependence on k being ksqrt{k}, improving on recent work by Knauer et al. who gave a simple algorithm that runs in linear time, for fixed values of k; the dependence on k was 2k.
The meeting was brought to a fitting close by Anders Claesson and Sergey Kitaev, two of the members of the ICE-TCS combinatorics group, who presented an accessible survey of work within the area of permutation patterns. A (permutation) pattern is a permutation of a totally ordered set. An occurrence of a pattern P in a permutation p is a subsequence of letters of p whose relative order is the same as that of the letters in P. As an example, the permutation 461352 has three occurrences of the pattern 321, namely the subsequences 432, 632 and 652. In 1969 Don Knuth pioneered this work by showing that the stack sortable permutations are exactly the 231-avoiding permutations. Anders and Sergey gave a brief introduction to the field, starting with a presentation of Don Knuth's result.
The symposium was attended by about 25 participants. Unfortunately, not many staff members from the local computer science departments were present at the talks. However, it was pleasing to see that several MSc students in Computer Science and Mathematics showed intellectual curiosity and attended the whole event. This bodes well for the future of research in (Theoretical) Computer Science in Iceland.
I myself believe that we should teach our postgraduate students that attending talks is a fundamental part of their scientific upbringing, and that we should teach this, like everything else, by example. The worst that can happen when attending a talk is that one learns at least about the existence of some research area or result that increases one's knowledge of Computer Science as a whole. And, who knows, maybe that knowledge may even turn out to be useful in our own work tomorrow. In research often help comes from the most unexpected sources.
The second symposium was graced by the presence of three outstanding keynote speakers from outside Iceland, namely Wan Fokkink, Jan Kratochvil and Moshe Vardi. The presentations by the invited speakers were complemented by 25 minute talks delivered by Ragnar K. Karlsson, Magnús M. Halldórsson, Anders Claesson/Sergey Kitaev (who shared the closing slot) and myself.
The morning session was devoted to "Volume B" talks. Moshe gave the meeting the best of starts with a talk describing the design of the ForSpec Temporal Logic (FTL), the new temporal logic of ForSpec, Intel's new formal property-specification language, which is today part of Synopsis OpenVera hardware verification language. The focus of Moshe's talk was on design rationale, rather than a detailed language description, and during the presentation he offered a very accessible discussion of the field of model checking, of linear and branching time temporal logics, and of the automata-theoretic approach to LTL model checking. Moshe also told the audience that his analysis of the relative merits of LTL and CTL has been referred to as "character assassination" by some of our colleagues :-)
Moshe's talk was immediately followed by the second keynote address, which was delivered by Wan Fokkink. Wan's talk presented joint work with Bard Bloom, Rob van Glabbeek and Paulien de Wind devoted to the systematic derivation of congruence formats for various behavioural equivalences in the linear-time/branching-time spectrum from decomposition results for the modal logics that characterize them.
I closed the morning session with a talk presenting joint work with Taolue Chen, Wan Fokkink and Anna Ingólfsdóttir on the axiomatizability of bisimulation equivalence over the language BCCSP extended with the priority operator.
The afternoon session was devoted to "Volume A" talks. The first talk in that session was delivered by Jan Kratochvil, who presented a survey of work on graph homomorphisms, viz. edge-preserving vertex mappings between two graphs. He showed how the use of graph homomorphisms unifies previously defined and independently studied notions such as graph covers, role assignments, and distance constrained graph labelings. Jan surveyed recent results and open problems related to these notions, with special emphasis on the computational complexity issues. He also mentoned connections to the Constraint Satisfaction Problem and the Dichotomy Conjecture.
Graphs featured also in the two 25 minute talks that followed Jan's address. The first talk was delivered by Ragnar Karlsson, who had defended his MSc thesis the day before. (For the record, Ragnar is the first MSc student to graduate under the suprvision of a member of ICE-TCS, viz. Magnús M. Halldórsson. Congratulations, Ragnar!) Ragnar presented the main results in his MSc thesis related to so-called strip graphs. These graphs are formed by an interval graph together with an equivalence relation on the vertices, and can be used to model the classic Job Interval Selection Problem (JISP) on one machine. In this problem, the input is a set of jobs, each of which is a set of intervals, and the object is to select at most one interval from each job such that no two chosen intervals intersect. This corresponds to being given multiple possible run-times for each job and trying to schedule as many jobs as possible. This problem is known to be NP-complete. However, strip graphs provide a very nice way to model the input of this graph and, by using structural observations of the input, Ragnar was able to find a fairly efficient exponential algorithm to solve this problem.
Magnús M. Halldórsson presented the next 25 minute talk, reporting on joint work with Takeshi Tokuyama and Alexander Wolff. The scientific director of ICE-TCS considered the problem of computing a non-crossing spanning tree of a graph that has been embedded in the plane. This problem is known to be NP-hard. During his talk, Magnús considered the complexity of the problem in terms of an input parameter k: the number of pairs of edges that cross. He gave an algorithm with a dependence on k being ksqrt{k}, improving on recent work by Knauer et al. who gave a simple algorithm that runs in linear time, for fixed values of k; the dependence on k was 2k.
The meeting was brought to a fitting close by Anders Claesson and Sergey Kitaev, two of the members of the ICE-TCS combinatorics group, who presented an accessible survey of work within the area of permutation patterns. A (permutation) pattern is a permutation of a totally ordered set. An occurrence of a pattern P in a permutation p is a subsequence of letters of p whose relative order is the same as that of the letters in P. As an example, the permutation 461352 has three occurrences of the pattern 321, namely the subsequences 432, 632 and 652. In 1969 Don Knuth pioneered this work by showing that the stack sortable permutations are exactly the 231-avoiding permutations. Anders and Sergey gave a brief introduction to the field, starting with a presentation of Don Knuth's result.
The symposium was attended by about 25 participants. Unfortunately, not many staff members from the local computer science departments were present at the talks. However, it was pleasing to see that several MSc students in Computer Science and Mathematics showed intellectual curiosity and attended the whole event. This bodes well for the future of research in (Theoretical) Computer Science in Iceland.
I myself believe that we should teach our postgraduate students that attending talks is a fundamental part of their scientific upbringing, and that we should teach this, like everything else, by example. The worst that can happen when attending a talk is that one learns at least about the existence of some research area or result that increases one's knowledge of Computer Science as a whole. And, who knows, maybe that knowledge may even turn out to be useful in our own work tomorrow. In research often help comes from the most unexpected sources.
Saturday, June 03, 2006
And Logic Begat Computer Science
Last Thursday, 1 June, ICE-TCS@Reykjavík University hosted a public lecture by Moshe Vardi. This public lecture, entitled "And Logic Begat Computer Science: When Giants Roamed the Earth", was probably the event with the highest profile that we have hosted so far, was heavily advertised and was attended by over one hundred people. (Chairs had to be brought in the room to accommodate the audience, and people were sitting along the aisles of the lecture theatre.)
During the talk, Moshe provided an overview of the unusual effectiveness of logic in computer science by surveying the history of logic in computer science, going back all the way to Aristotle and Euclid, and showing how logic actually gave rise to computer science. This was an erudite and witty lecture, full of memorable one liners that I'll try to transcribe one day. For example, Moshe said that
"Aristotle was the most influential intellectual of all times, whose wisdom stood unchallenged for over 2000 years. Now we hope for two years!"
and treated the men in the audience with a quotation from Words of Power, by Andrea Nye:
" Logic, one current argument goes, is the creation of defensive male subjects who have lost touch with their lived experience and define all being in rigid propositional categories modelled on a primal contrast between male and female."
Above all, I believe that each person in the audience learned something new about the history of thought that led to the development of computer science as we know it, and about the lives of the people involved. I for one certainly did and loved every minute of it.
People who enjoyed Moshe's talk will want to seek out and read the lovely book Engines of Logic by Martin Davis.
Moshe's talk was taped, and will soon be available on the web. I'll post the URL on these pages in due course.
During the talk, Moshe provided an overview of the unusual effectiveness of logic in computer science by surveying the history of logic in computer science, going back all the way to Aristotle and Euclid, and showing how logic actually gave rise to computer science. This was an erudite and witty lecture, full of memorable one liners that I'll try to transcribe one day. For example, Moshe said that
"Aristotle was the most influential intellectual of all times, whose wisdom stood unchallenged for over 2000 years. Now we hope for two years!"
and treated the men in the audience with a quotation from Words of Power, by Andrea Nye:
" Logic, one current argument goes, is the creation of defensive male subjects who have lost touch with their lived experience and define all being in rigid propositional categories modelled on a primal contrast between male and female."
Above all, I believe that each person in the audience learned something new about the history of thought that led to the development of computer science as we know it, and about the lives of the people involved. I for one certainly did and loved every minute of it.
People who enjoyed Moshe's talk will want to seek out and read the lovely book Engines of Logic by Martin Davis.
Moshe's talk was taped, and will soon be available on the web. I'll post the URL on these pages in due course.
Subscribe to:
Posts (Atom)