Monday, June 30, 2008

PhD interviews

Last week we interviewed most of the applicants for our department's PhD studentships that are due to start in September. (I was on the interview panel; note that I am PhD admissions tutor.) Subsequently I have sent out some informal offers by email. We had two kinds of studentship on offer: doctoral training account (DTA) studentships (given out by the research councils and only available to Uk students) and department funded ones (available to EU students).

The DTA studentships were allocated very late this year, at the end of April, which is the fault of the research councils, which are clearly out of touch with the process. They don't seem to appreciate that a highly-qualified, well-organised student will want to have a place stitched up round about Jan/Feb. Add to that the constraint to UK students, and you begin to see why it was more fun to fill the department-funded places. The late allocation of the DTA quota is the second-most annoying thing that has happened to me this year; the most annoying thing is conveniently co-located in my previous post to this blog.

Having said which, I concede that we should probably try to raise our game vis-a-vis the process of advertising to prospective students.

Monday, June 09, 2008

Dog Bites Man

As hinted in this earlier post, I learned that a recent grant application of mine just failed. (It was joint with colleagues here and at Warwick, on the general topic of algorithmic game theory.)

Now, I have good reason to be very dissatisfied with the way the grant application was treated, but I won't do the details just now. For the moment, here are a couple of more "philosophical" observations.

  • It costs you nothing to submit a proposal (except in considerable time spent preparing it), and it gets vetted by unpaid volunteers. You get what you pay for!

  • In Fleet Street, "man bites dog" is news, but "researcher's grant application fails" is most definitely not news.

Campaign for the University of Oxford

Today I receive some literature on behalf of the Campaign for the University of Oxford, in my humble capacity of an alumnus. Since I work for another university I don't feel that inclined to contribute. Actually, I guess that employees of Oxford Univerity itself are probably the poorest prospects in that respect.

The first "campaign for Oxford" was begun while I was a student there; the student union at the time was opposed to it, for reasons which didn't make sense to me at the time. I understand that that earlier campaign was quite successful.

The case being made in the literature that I received, is trapped in a kind of contradiction, which is that it is based on the current success of the university, to the point that one might ask why they need more money, if they are already doing so very well. On the other hand, the Matthew effect is so widespread in academic life, that it stands a good chance for that reason.

Saturday, June 07, 2008

No longer young

Last week's Times Higher had a feature (pp. 30-35, and front cover) on "Rising Stars: The young academics who are tipped to go places". Their definition of "young" was the most liberal I have seen, namely 40 or younger. Only a few weeks ago I would have qualified! Damn.

Incidentally, one of those who made that hall of fame (in the capacity of "the philosopher") is social choice theorist Christian List at LSE, who is on the COMSOC program committee and is going to give a tutoral at the workshop. Kudos to my co-chair Ulle Endriss for recruiting him to these tasks.

A recrudescence of the national debate about the importance of mathematics saw Ben Goldacre calling into question the case for more maths teaching. This article by Simon Jenkins in the Guardian, attempts to do the same. He dismisses the value of intellectual disciplines that purport to train the mind, and alleges that promotion of such study "panders to the political correctness of the conservative classes". Maybe I should just admit myself to be a member of those evil "conservative classes" that he deplores. Winston Churchill supposedly said that you don't have a heart if you are not a socialist before age 30, and you don't have a brain if you are not a Tory after that. I guess that makes me about 10 years too late.

Tuesday, June 03, 2008

definition of computational complexity

This post on the Fortnow/Gasarch blog caught my eye, partly because some of my own work is cited, towards the end. In the post, Lance Fortnow argues that proofs of NP-completeness do not constitute work in computational complexity, but rather in algorithms. This is because a typical NP-completeness proof consists of an efficient algorithm that translates an instance of some pre-existing NP-complete problem, into a corresponding instance of the problem of interest.

Lance's dividing-line between "algorithms" and "computational complexity" disagrees with a passage of text I wrote for one of the pages of my research group, in which I said: This kind of analysis belongs to two closely-related research fields: algorithmics, the design of algorithms with provable performance guarantees, and computational complexity, the classification of problems according to the kinds of algorithms that can solve them. According to what I wrote, an NP-completeness result is a work of computational complexity, albeit not usually a very interesting one.

I would not be that interested in getting into a debate about where exactly to draw this dividing-line. But I tend to prefer my own definition, mainly because it defines computational complexity in terms of what it is, rather than what it isn't. The other problem with Lance's definition is that one can imagine some Grand Inquisitor of Computational Complexity, managing to exile all sorts of results from the hallowed halls of computational complexity to the chilly uplands of algorithms, on the grounds that they are often tainted with algorithmic content. Take for example Savitch's Theorem, and its corollary that nondetermistic polynomial space is equivalent to deterministic polynomial space. The proof uses the reachability method, which is clearly an algorithm.