Archive for August, 2010

ICM2010 — Ngô laudatio

August 21, 2010

Before I continue with brief descriptions of the laudationes, let me mention that Julie Rehmeyer has written descriptions of their work for a general audience and Terence Tao has now posted about the work of the Fields medallists and the other prizewinners. And as I have already said, the ICM website has links to the full texts of the laudationes themselves. So anybody now wanting to understand the mathematics has an excellent starting point, and I am free to concentrate on the more frivolous details of the talks, perhaps slipping in the odd mathematical comment as I do so.

Jim Arthur went next. His was the terrifying task (though much less terrifying for him than for most) of explaining the work of Ngô Bảo Châu to a general mathematical audience. I’d say that he did about as well as it is possible to do, which meant that he was able to convey some of the flavour, but obviously without managing to transmit to the non-expert the sort of wisdom tht it takes the experts in this particular area years to accumulate.

ICM2010 — Lindenstrauss laudatio

August 20, 2010

After the unceremonial closing of the opening ceremony it was lunch time. I soon found myself in the first of what would turn out to be many queues of the kind where the optimal strategy is far from obvious but obviously not very good. One of the army of volunteers (the males of whom were wearing smart purple Indian shirts — collarless and going down to the thigh) told me to go up a floor, so I did, and I found a number of parallel queues. There was also a borderline-legitimate queuelet round to the side, and I joined that, hoping that it was legitimate enough not to annoy people and not too far to the side to get the attention of the people serving lunch. Lunch was basically an Indian takeaway — a choice of various Indian dishes served in an aluminium tray and a white cardboard lid that was rectangular apart from being curved off at the vertices, and held in place by a fold at the top of the aluminium. (I’m not certain it was aluminium but that’s my best guess.) After about 15 minutes of anxious waiting I was in a position to ask for lamb biryani, which I had also had for breakfast. It cost me two coupons from my kit bag, and came with a small pot of yoghurt, and the option of a fierce looking chutney, which I took. (I was about to say “took with relish” but then realized that to some people that would be ambiguous.) I was told that if I wanted to sit down I could go into the gallery of the main hall, so I did. A table would have been nice, but I could manage without.

The lamb biryani was slightly disappointing in that it had just one piece of lamb which, though large, was about 80% bone. That left quite a lot of rice to get through, and I was glad of the opportunity to spice it up with the chutney. For what it’s worth, we were provided with small wooden disposable spoons and forks to eat with. The chutney passed a basic test: it made my nose run.

ICM2010 — Opening ceremony, continued

August 20, 2010

I’d got up to the awarding of the Nevanlinna prize to Dan Spielman. Next up was the Gauss prize. Yves Meyer came up on stage with a dark blue jacket and dark grey trousers (both dark enough that you had to look hard to see that they didn’t form a suit). We were told that he had “created a new way of multiresolution thinking,” a conclusion that would be hard to dispute. He had a grey beard and moustache and a vigorous handshake. This was the second ever Gauss prize, the first going to Ito in Madrid in 2006.

An even newer prize followed, the first award of the new Chern prize for lifetime achievement. This is an interesting prize in that it comes with a lot of money — half a million dollars (some of it from Chern’s family and some from the Simons foundation, about which more later) — which is split 50-50 between the recipient and good mathematical causes nominated by the recipient. I wonder if we will get to hear how Nirenberg decides to spend the charitable half. (Update: I’ve just discovered on the web that he’s giving it to the Courant Institute.) Nirenberg had white hair, beard and moustache, and did not smile.

After that was all over, the president (of India, not the IMU) told us once again what the ICM was, but after that unpromising start she moved into a speech about India’s mathematical heritage and various other topics, all discussed in a way that made it clear that somebody — I presume not her — knew what they were talking about. She told us of an old Sanskrit saying, “Mathematics stands at the helm of all sciences.” I think I prefer the “queen of” metaphor that is more prevalent in the west. She told us that the concept of zero originated in India, and that calculus was anticipated in India in the 15th century. I wondered before the opening ceremony started how many times Ramanujan would be mentioned. There was a mention here, and a few others, but I forgot to count. At one point the president referred to India’s rich cultural heritage twice in successive sentences. There was plenty about the impact of mathematics in technology, economics, cultural life — you get the idea. But this was a pretty good speech as such things go, and the president seemed intelligent, and young for her years.

ICM2010 — more on the opening ceremony

August 19, 2010

Let me try to give a stream-of-consciousness description of the opening ceremony, by which I mean translate the notes I feverishly took into continuous prose and not do much else to them.

I booked my hotel fairly late in the day, for the obvious reason that if I left it longer, the work needed would be identical but I would have less choice. And so it turned out: instead of staying in the hotel right next to the congress (so much so that you can get from one to the other without going out of doors) I am, as I mentioned in my first post, about 40 minutes away. The disadvantages of this are obvious — I can’t nip back to my room to get something, and I have to worry each day about how I’m going to get to and from the hotel. But the hotel itself is nice, and I quite like getting to know the city a bit rather than being cocooned in the conference area the whole time.

This morning they laid on buses to take people from the hotels to the congress (as they will every morning). I had had dire warnings about traffic, and been told to expect a two-hour journey, which would still have been quick enough to get to the opening ceremony on time but would have left me slightly anxious. As it was, the journey took the usual 40 minutes or so, so I got to the HICC at about 8.30. We had been told to be in our seats by 10.30, so I thought I had a couple of hours to kill. However, this turned out to be a miscalculation on my part.

ICM2010 — opening ceremony in brief

August 19, 2010

The laudationes start in half an hour, so all I have time for is a few headlines (though you will almost certainly have these from other sources).

The Fields medals went to Elon Lindenstrauss, Ngô Bảo Châu, Stanislav Smirnov and Cedric Villani. The Nevanlinna prize was awarded to Dan Spielman. The Gauss prize went to Yves Meyer and the Chern medal was given to Louis Nirenberg. The Laudationes for the Fields medals and Nevanlinna prize will be given by Hillel Furstenberg, Jim Arthur, Harry Kesten, Horng-Tzer Yau and Gil Kalai, respectively, and I’m looking forward to them. I’ll admit now that I was on the Fields medal committee — a difficult job, and moreover one that means that there are things that I cannot discuss on this blog (not that in any case I would like to engage publicly in discussions about whether the right decisions were made). What I can say is that the four people who have won Fields medals have spectacular achievements to their names.

Other interesting news was that the next ICM will be in South Korea (in Seoul), that the next IMU president will be Ingrid Daubechies, the first woman to hold the post, and that if you type “ICM” into the IMU web page you can now find every single article that has ever appeared in an ICM proceedings, and that this database is searchable.

I’ll describe the opening ceremony in more detail in my next post. I’ll include a description of what the prizewinners were wearing. (If you look up Cedric Villani in Google images, you’ll see that this is a more interesting question than you might at first think.)

That’s it for the time being.

ICM2010 — first impressions

August 18, 2010

I’m writing this post from a hotel room in Hyderabad at 3.20pm, trying to stay up for exactly the right length of time to deal with any jet lag I might have: stay up too little and I’ll wake up tomorrow morning at 4am and be unable to get back to sleep and will then still have the problem to deal with tomorrow; stay up too much and instead I’ll be woken tomorrow by my alarm and will desperately not want to get up, which would be bad as then I would miss the bus that will take me to the International Convention Centre for the opening ceremony of ICM2010. By the intermediate value theorem, there must be an optimal time to collapse into bed (given data such as the time change and the small bits of sleep I snatched between London and Dubai and between Dubai and Hyderabad). Unfortunately, I don’t know how to work it out.

So I’m guessing about 6.30pm, which would allow me to sleep for twelve hours and still comfortably make the bus. And to keep myself awake for the next three hours I plan to write this post and complete another more mathematical one that I started a few days ago. And over the next few days, if I can find the time, I thought I might write a traditional-style ICM blog. After all, for every one of the many mathematicians who are here there are dozens who are not. Perhaps some of those would have liked to come but couldn’t quite face organizing a trip all the way to Hyderabad. And perhaps some of those wouldn’t mind being kept in the loop, so to speak. (more…)

A possible answer to my objection

August 14, 2010

It seems that the informal argument in my previous post may have been aiming off target. Here is a sort of counter to it, by Jun Tarui. (See also this earlier comment of his, and the ensuing discussion.)

If I’ve understood various comments correctly, Deolalikar is making a move that I, for one, had not thought of, which is to assume that P=NP and derive a contradiction. How could that help? Well, it allows us to strengthen any hypothesis we might like to make about polynomial-time computable functions to one that is preserved by projection.

Let me spell that out a bit. Suppose that f is a polynomial-time computable function on n+m bits, where m is at most polynomial in n. Then we can fix a set A of n bits, and for each x\in\{0,1\}^A we can ask the question, “Does there exist y\in\{0,1\}^{A^c} such that f(x,y)=1?” (By (x,y) I mean the sequence that agrees with x on A and with y on A^c.) And we can set g_A(x)=1 if and only if the answer is yes.

Could anything like Deolalikar’s strategy work?

August 13, 2010

This post comes with the same warning as my previous one: my acquaintance with the ideas of Deolalikar’s paper is derived not from the paper itself (apart from a glance through it to get some kind of general impression) but from some of the excellent commentary that has been taking place on the blogs of Dick Lipton and Scott Aaronson. One comment that many people, including me, have found very useful has been one of Terence Tao, who attempted to summarize the state of the discussion up to the time he made the comment. Here is a portion of his summary.

The paper introduces a property on solution spaces, which for sake of discussion we will call “property A” (feel free to suggest a better name here). Formally, a solution space obeys property A if it can be efficiently defined by a special family of LFP formulae, the monadic formulae (and there may be additional requirements as well, such as those relating to order). Intuitively, spaces with property A have a very simple structure.
Deolilakar then asserts
Claim 1. The solution space to P problems always obey property A.
Claim 2. The solution space to k-SAT does not obey property A.

The latest from Dick Lipton’s blog seems to be that Neil Immerman has identified two serious flaws with Deolalikar’s proof. However, Tao, commenting on that, has pointed out that Deolalikar’s general strategy has not yet been shown to be hopeless in the way that, say, an attempted natural proof would have been shown to be hopeless by Razborov. In this post, I’d like to argue that it might be hopeless. I’m not sure I can say what that means in the abstract, so let me just give the argument. (more…)

My pennyworth about Deolalikar

August 11, 2010

Given that I have expressed rather unambiguously an interest in the P/NP problem on this blog, I feel duty bound to make some kind of remark about Deolalikar’s recent attempt to prove the theorem. (If by some extraordinary chance you don’t know what I am talking about, then an excellent starting point is Dick Lipton’s blog, a link to which can be found in my blogroll.)

The problem is that I haven’t looked at Deolalikar’s paper in any detail, and already I can tell that I cannot possibly compete with the extremely knowledgeable comments that have been made by several TCS experts. So instead, let me say that, like everybody else, I greatly admire what Deolalikar has done, whether or not it turns out to be correct, and am happy to wait to see how things pan out.

Instead of commenting directly on his work, I thought I’d air some thoughts I had a few years ago. I was reminded of them by reading that an important feature of Deolalikar’s proof is that it uses uniformity in an essential way (though whether this is really the case has been disputed by some commenters). (more…)