Author Archives: wilson.mark.c

The remarkable Donald Knuth

On the occasion (today in the USA) of Don Knuth’s 70th birthday, several bloggers have posted tributes (see Jeffrey Shallit’s list). His list of achievements is really impressive, and he has had a big influence on me. To name a few areas, somewhat facetiously: his founding of the field of analysis of algorithms (AofA) led to the development of a community of people who are heavy users of generating function methodology and therefore may be interested in my research in that area, and it gave me something nice to teach as a mathematician moving into a CS department! More seriously, I can’t conceive of computer science as a real science without proper analysis of algorithms, and I would hate to have to write papers without using TeX.

Since unalloyed praise can get a bit cloying, I will mention that it might have been better for the world if Knuth (or someone else) had been able to build a school of AofA in the USA. The algorithms community in the USA is heavily dominated by “worst-case” analysis and indeed by analysis of problem complexity, which is a very weak form of analysis of algorithms, concentrating as it does on lower bounds and rather weak (many would say useless) upper bounds.

The main development of AofA along Knuthian lines has been in Europe, in France (Philippe Flajolet and others) and Austria particularly. In recent years Bob Sedgewick and others have tried to bridge the gap between these communities through meetings such as ANALCO, but at least to my eyes they have not yet had great success.

Of course some may say that the sort of very detailed analysis by Knuth is unnecessary for a working computer scientist. And even if his analyses made sense in the days of flat memory, the prevalence of such things as caching makes it impossible to make such detailed predictions nowadays. But perhaps we just need some better mathematics.

Goodness, greatness

During an enforced period of recuperation I have been thinking about various “big issues” in life. One is the relation between goodness, by which I mean consistent behaviour according to a moral code that places a high weight on the welfare of others, and greatness, by which I mean consistent highly skilled performance at some activity.

The “myth of monolithic personality” described by Gian-Carlo Rota (every great person is also good, and great at everything) was probably created by rulers seeking to show their subjects how godlike they were. I doubt that many people believe this nowadays. In fact the opposite idea, that goodness is inversely correlated with greatness, is surely more common. It seems plausible: after all, we only have so much energy, and acquiring great skill requires a lot of time spent practicing, not to mention introspection.

In the musical Chess, by Tim Rice and half of ABBA, the Russian (world chess champion) and his ex-wife trade recriminations which express this (perceived) selfishness of the great:

“Anyone can be a husband, lover / sooner them than me, when they discover / domestic bliss is shelter for their failing / Nothing could be worse than self-denial / having to rehearse the endless trial / of a partner’s rather sad demands prevailing”

“As you watch yourself caring / about a minor sporting triumph sharing / your win with esoterics, paranoids, hysterics / who don’t pay attention to / what goes on around them, they leave the ones they loved the way they found them / a normal person must dismiss you with disgust / and weep for those who trusted you”.

My question is: what theoretical reasons are there for this alleged inverse correlation? There are numerous examples of high achievers who appear to have happy personal lives, and of course many who don’t. Are there hidden variables here – for example, the type of endeavour in which greatness is being sought (how competitive is it, intrinsically?), the performance level versus the maximum potential performance (are the really top people less stressed and therefore nicer than the ones just a little below, who don’t have as much talent and compensate by selfish overwork?), etc. In other words, could we have a decent theory that answers: when, and why, is a genius likely to be a jerk?

Humour: the Richter Scales

Will there be another bursting bubble in the computer industry? Listen to this catchy tune …

http://www.youtube.com/watch?v=fi4fzvQ6I-o

(looks like this link no longer works, due to “a copyright claim by a third party”)

However, this one seems to work.

I’ve got a little list

I wrote and performed this while a graduate student at UW-Madison. It can be adapted to any local academic environment quite well (lots of lines ending in “ist”). I can’t quite remember all the targets I took aim at in those days, but I’m sure they all deserved it. 🙂

[To the tune of “I’ve got a little list” (Mikado – Gilbert and Sullivan)]
[By Mark Wilson 1992 – first performed September 1992]

As some day it may happen that the budget must decay,
I’ve got a little list – I’ve got a little list,
Of mathematical offenders who might well be sent away,
And who never would be missed – who never would be missed!

There’s the pestilential lecturers who won’t define their terms,
Like CLT-groups, n-jets and biholomorphic germs .
All speakers who can’t tell the time or see you’re there no more,
All speakers who wish earnestly to chitchat with the floor,
And the picture-drawing low-dimensional topologist,
They’d none of ’em be missed – they’d none of ’em be missed!

CHORUS. He’s got ’em on the list – he’s got ’em on the list,
And they’ll none of ’em be missed – they’ll none of them be missed.

There’s the nonsmoking crusader and the others of his race,
And the all-but physicist – I’ve got him on the list!
All category jugglers who would live in twistor space,
They never would be missed, they never would be missed!
The people who embark on proofs without hypotheses,
Insert, delete and alter them in any way they please.
The hapless student who believes on every single day,
“if P yields Q then Q yields P”, and then demands an ‘A’.
And those singular anomalies, applied set theorists,
I don’t think they’d be missed – I’m sure they’d not be missed!

CHORUS. He’s got them on the list – he’s got them on the list,
And I don’t think they’d be missed – I’m sure they’d not be missed!

And that outgrowth of heuristics who the calculus would save,
The nonstandard analyst – I’ve got him on the list!
All axiom-stretchers, lemma freaks, and definition slaves,
They’d none of ’em be missed – they’d none of ’em be missed.
And insufferable support staff of an antisocial kind,
Such as what-d’ye call her, thing-em-bob, and likewise – never mind.
And ‘St-‘St-‘St- and What’s-her-name, and also You-know-who –
The task of filling in the blanks I’d rather leave to you.
But it really doesn’t matter whom you put upon the list,
For they’d none of ’em be missed – they’d none of ’em be missed!

CHORUS. You may put ’em on the list – you may put ’em on the list;
And they’ll none of ’em be missed – they’ll none of ’em be missed!

Public relations and social capital for nerds

I just went to a nice talk by Michael Trick at the 42nd ORSNZ Conference being held at the University of Auckland today and tomorrow. The gist of it was that while Operations Research as a subject is doing really well, with many interesting applications arising in the service sector of the economy in particular, the OR societies are not thriving and it does not have a clear “brand” at least in the public mind. This is partly because of the “Bowling Alone” phenomenon described by Robert Putnam (less engagement in any sort of civic activity by younger people), partly because the very success of the field makes it more likely to fragment, and partly because of a lack of effort at cohesion. He urged the use of new technology (blogs, etc) to try to create more sense of community and focus.

The theoretical computer science community have realised that even within computer science their contribution is greatly misunderstood (see the Theory Matters wiki), and convincing the public is likely to be much harder. I would love to hear from anyone who knows the most effective way to address this problem of correcting misperceptions. It causes problems like the job market time lag and other evils, and we academics really need to attack it more seriously.

Research funding in New Zealand: more money, less form-filling needed

I recently came across a submission by Nicholas Wormald (who a long time ago worked in the building where I am now) to the 2005/6 National Strategic Review of Mathematical Sciences in Australia. Two things stood out for me: how similar Australian government ideas are to those in New Zealand, and how different they seem to be from those in Canada. The rejection rate for the only serious fund for “pure” research in NZ, the Marsden Fund, is about 93%, resulting in much cynicism and quite likely a Matthew effect (one of my pet hates – I would love to see evidence that giving so much more money to the already successful is somehow better for science overall). It seems clear that many proposals are rejected simply for lack of funding, not because of any problem with the proposal. The Canadian NSERC system appears much more enlightened: smaller grants, spread more widely, with less paperwork.

If it makes sense to do so, please sign the Marsden Fund Open Letter from the New Zealand Association of Scientists, requesting a tripling of the fund.

Come to New Zealand for algorithms/combinatorics in 2008

I am involved in organizing two conferences in 2008 (both in summer in nice places to visit!)

Napier, 18-22 February, sponsored by NZIMA, with invited speakers Michael Mitzenmacher (Harvard), Dominic Welsh (Oxford), Steve Linton (St Andrews), Brendan McKay (ANU Canberra), Michael Langston (Tennessee).
Auckland 15-19 December, Fourth International Conference on Combinatorial Mathematics and Combinatorial Computing (4-ICC).

The first is aimed at creating more of a recognized community in the general area of algorithms in NZ (rather than isolated researchers who work on algorithms and applications), and will include many informal sessions and much free time. Costs for NZ students are essentially zero and other subsidies are available. Participant numbers are limited to 60; we currently have some free spaces.

This conference is part of a 6-month NZIMA programme on Algorithms. There are other activities planned including public lectures around the country by David Harel (Weizmann Institute). There is a possibility of another meeting later in the year.

The 4-ICC is in a series of meetings (building on smaller more frequent ones like ACCMCC) that occurs every 10 years, and about 150-200 participants are expected. Details will become available later. If you have never been to New Zealand and have some interest in these research areas, 2008 would be an excellent time to come!

Open source mathematical software!

For many years I have wondered why there was no open-source alternative to Maple, Mathematica and the like. The November 2007 Notices of the American Mathematical Society has an opinion piece discussing this and advocating such a thing. The authors are involved in producing just such an alternative, called SAGE. Written in Python, it seems very promising. It has interfaces to Magma, Maple, Mathematica, MATLAB, and MuPAD, and the free programs Axiom, GAP, GP/PARI, Macaulay2, Maxima, Octave, and Singular. Try it out!

The job market time lag: why?

Yet another press article has come out (Tech sector needs to be sexier) saying that the computer industry has a serious skills shortage. At the same time enrolments have been dropping in the CS area over several years, and not just in New Zealand, but worldwide. Again we are being told that the parents and guidance counsellors are giving poor advice to high school students, and not explaining just how strong their prospects of interesting and well-paid jobs are.

Is there a coherent theory that explains this sort of mismatch? It has been several years now – why do parents and guidance counsellors take so long to get the message? Don’t they look at any evidence and predictions by analysts? On what do they base their ideas? It seems rather odd to give advice to teenagers that may have a major impact on their future without using some rigorous analysis. Or am I missing the point?