Monday, November 17, 2014

Oxford Algorithms: faculty position, studentships

Oxford University will shortly be announcing a (permanent) faculty position in Algorithms and Complexity. The official advertisement will appear on our web page early in 2015.

The department also has a bunch of new doctoral studentships advertised here. Quoting the ad: Following a generous donation by Google, the Department of Computer Science at the University of Oxford is delighted to invite applications for up to 15 fully-funded DPhil (Oxford’s PhD) studentships tenable from 1st October 2015.

The studentships are available for research in any area represented in the department.

Friday, October 17, 2014

Oxford Algorithms Day 2015

The Oxford Algorithms Day will take place on the 15th April 2015. It's the latest in a series of one-day algorithms meetings that have been held on an ad-hoc basis at various UK universities that have algorithms/computational complexity research groups. Below is a list of previous similar events, most of which have better acronyms than this one.

2014 (MAD):
2013 (QMAD) :
2012 (Oxford’s Algorithms Workshop, 2 days):
2010 (BAD):
2010 (ACiD, 3 days):
2009 (BAD):
2008 (DIMAP):
2008 (LAD):
2007 (ACiD, 3 days):
2006 (ACiD, 3 days);
2005 (ACiD, 3 days);
2003 (LAD):
2002 (WAD) Warwick: Speakers: Claire Kenyon (Mathieu), Uri Zwick, Muthu Muthukrishnan,
Ian Stewart, Tomasz Radzik, Richard Brent, Leszek Gasieniec, Vladimir Deineko
2001 (WAD) Warwick: Speakers: Richard Cole, Wilfrid Kendall, Martin Dyer, Paul Goldberg,
Graham Brightwell, Mark Jerrum, Leszek Gasieniec, David Manlove
1999 (LAD):

Monday, September 29, 2014

Call for Nominations for EATCS Fellows 2015

Luca Aceto has already advertised on his blog the calls for nominations for the Presburger award and the EATCS Distinguished Dissertation award; see the details at those links or on the EATCS web site. Here’s another one:

Call for Nominations for EATCS fellows 2015 : December 31, 2014


Please note: all nominees and nominators must be EATCS Members

Submit by December 31 of the current year for Fellow consideration by email to the EATCS Secretary ( The subject line
of the email should read "EATCS Fellow Nomination - <surname of candidate>".


The EATCS Fellows Program is established by the Association to recognize outstanding EATCS Members for their scientific achievements in the field of Theoretical Computer Science. The Fellow status is conferred by the EATCS Fellows Selection Committee upon a person having a track record of intellectual and organizational leadership within the EATCS community. Fellows are expected to be “model citizens” of the TCS community, helping to develop the standing of TCS beyond the frontiers of the community.

In order to be considered by the EATCS Fellows Selection Committee, candidates must be nominated by at least four EATCS Members. Please verify your membership at

The EATCS Fellows-Selection Committee consists of

  • Rocco De Nicola (IMT Lucca, Italy)
  • Paul Goldberg (Oxford, UK)
  • Anca Muscholl (Bordeaux, France)
  • Dorothea Wagner (Karlsruhe, Germany, chair)
  • Roger Wattenhofer (ETH Zurich, CH)


A nomination should consist of answers to the questions below. It can be co-signed by several EATCS members. At least two nomination letters per candidate are recommended. If you are supporting the nomination from within the candidate’s field of expertise, it is expected that you will be specific about the individual's technical contributions.

To be considered, nominations for 2015 must be received by December 31, 2014.

1. Name of candidate

Candidate's current affiliation and position

Candidate's email address, postal address and phone number

Nominator(s) relationship to the candidate

2. Short summary of candidate's accomplishments (citation -- 25 words or less)

3. Candidate's accomplishments: Identify the most important contributions that qualify the candidate for the rank of EATCS Fellow according to the following two categories:

A) Technical achievements

B) Outstanding service to the TCS community

Please limit your comments to at most three pages.

4. Nominator(s):


Affiliation(s), email and postal address(es), phone number(s)

Thursday, July 10, 2014

We need to talk about CDTs

A colleague from another UK university recently asked me about applying for a joint Centre for Doctoral Training (CDT) in algorithms and complexity, and I had to answer that as far as I know, there are no calls out for new CDTs, and there probably won’t be any new ones until the current CDTs come to an end, in 3-4 years’ time. Thus, for prospective doctoral students, for at least three years there will be a relative shortage of opportunities to work on algorithms and complexity, and if we later got the CTD in question, there would subsequently be a glut of such opportunities. This point is not specific to algorithms and complexity; you can apply it to your favourite research area. Furthermore, most CDTs are hosted by a single department, so if a student’s research area of interest is indeed catered-to by a CDT, they don’t have much choice about where to go.

That having been said, there are a couple of reasonable objections to the above points. The first one is that most students aged about 21 are not competant to set their own research agenda, or write a proposal. Choice and academic freedom are wasted on them. The second one is that the scholarly lifestyle is by nature rather peripatetic, especially in early-career, and this should be embraced by prospective graduate students, who should be eager to move to a different university.

The impact of CDTs on the academics who end up running them, or not as the case may be, is more open to criticism. I’ve heard complaints that they are onerous to administer, and that it can be hard to attract enough high-quality graduates to fill all the available places. They are also onerous to apply for in the first place, and may require the host institution to commit resources to them, which would otherwise have been free for other activities. If you’re not involved with a CDT, the fact that most PhD student funding goes to CDTs means that it’s hard to get PhD students. To summarise, you end up either overloaded or underloaded. These complaints are rarely aired in public, probably because they would reflect badly on the complainant.

Advocates of CDTs like to point to their “cohort effect” or “critical mass effect”. For a research student, it’s nice to have a couple of other students around who are working on projects related to one’s own, but you don’t actually need a dozen of them. PhD students should be encouraged to engage with their research communities, and not just each other. Recently at the ACM-EC conference I heard a bunch of impressive talks by graduate students who were clearly keen to develop their presence in the research community, and would not wish to be seen just as students.

Other aspects of the CDT system worth noting are the following. They fit in with a highly centralised, top-down system, in which national priorities are determined, and are then handed down to the academic community via funding decisions on their CDT applications. They also fit in well with the agenda to concentrate research funding on a small number of institutions. Come to think of it, those things may very will be their real raison d’être.

Monday, June 23, 2014

Gender balance and attitude to risk

An article in today’s Guardian, British researchers win £1.8m mathematics prize caught my eye. Subtitle: Britons among five winners of inaugural Breakthrough prize, which hopes to turn mathematicians into 'the new rock stars'. One of the founders, Yuri Milner is quoted as saying: "We think scientists should be much better appreciated. They should be modern celebrities, alongside athletes and entertainers," ..."We want young people to get more excited. Maybe they will think of choosing a scientific path as opposed to other endeavours if we collectively celebrate them more."

I think it could work. The spectacle of mathematicians making millions for their work could indeed attract young people into academic mathematics. There’s just one catch: it’s more likely to attract boys rather than girls, due to the male mentality being relatively risk-seeking. It’s a pretty safe bet that big prizes and celebrity status for a very few mathematicians, will serve as a stronger magnet for boys than for girls. And that, of course, is unhelpful to the objective of better gender balance in mathematics and science.

I’ve seen some severe criticism directed at various changes to academic life that have taken place during the past few decades. Some of these changes, for example, the general lament about hard money being displaced by soft money, could be regarded as changes that appeal to risk-seekers. However, I have not so far seen any criticism that considers their effects on gender balance.

Wednesday, October 23, 2013

article on privatisation of universities

I recommend the article Sold Out by Stefan Collini, in the London review of Books. It reviews two books about the process of privatisation/marketisation of higher education, that has taken place in the UK during the past roughly 30 years. Collini’s article provides a highly informative overview of the development and current state-of-play of private sector provision of HE, in the USA and UK. It then explains very lucidly the problems inherent in the current system of student funding, and is very convincing on why it cannot be expected to last. My only criticism: the article is passionate, but doesn’t propose remedial action. That may be because there’s a bigger picture (missing from the article) that includes, for example, the recent Royal Mail privatisation. According to this bigger picture theory, remedial action would not be specific to universities, but would involve a restoration of trust in public institutions and the public service ethic.

(added later:) ...And, this article (Economics students need to be taught more than neoclassical theory) in the Guardian looks relevant to the general topic. See also this earlier article (Economics students aim to tear up free-market syllabus). Their criticism of neoclassical economics is mainly that it failed to predict the financial crisis. It could also be blamed for an approach to student funding which takes the form of firstly, assuming all students are selfish agents, and secondly, repeatedly raising the price of higher education, in search of some kind of market equilibrium. 

Wednesday, October 09, 2013

What are the equilibria of this game?

In the course of writing a paper, we often construct examples of the sort of mathematical objects under analysis, as a means to figure out what’s true in general. Then the paper gets written, and the examples are stripped away, like the scaffolding from a completed building. Before it gets forgotten, I now provide an online description of the following game (that came up while writing this paper), since it sets you thinking about alternative solution concepts (exact/approximate Nash/correlated equilibria (well-supported or otherwise)), and which one(s) we are supposed to like best. Or maybe it could be used as part of a game theory exercise. (It may be helpful to point out that a well-supported ε-approximate equilibrium is one where no player ever uses a strategy that pays more than ε less than his best response. An approximate equilibrium that is NOT well-supported could allow some player to occasionally play a very poor strategy, provided that it’s with low probability.)

Suppose there are n players, numbered 1 through n. Each player has 2 pure strategies, call them a and b. Payoffs will be either 0 or 1, according to the following rule. Player 1 gets paid 1 to play a and 0 to play b, UNLESS all other players play a, in which case it’s the other way around. Meanwhile, for i>1, player i gets paid 1 to play the same way as player i−1 (otherwise is paid 0).

(If instead player 1 was paid to differ from player n, we would have a generalized Jordan game, with a unique Nash equilibrium where all players flip fair coins to choose a or b.)

So — spoiler alert — I reckon the answers are as follows. For exact Nash equilibrium, it’s not hard to see that players 1 and 2 can’t play pure strategies, and in fact players 1 and 2 should flip fair coins, meanwhile the other players all play 1. For exact correlated equilibrium, one solution (different from the NE) is for player 1 to flip a fair coin, while all the other players flip a single shared fair coin, ie they play the all-a’s vector or the all-b’s vector with equal probability. It looks like there is some freedom for any player to deviate slightly from this, while keeping it well-supported. In the neighbourhood of the original NE, only players 1 and 2 can deviate slightly, if we want the approximate equilibrium to be well-supported. (In fact, I think we can say more strongly, that all the well-supported Nash equilibria are in the vicinity of the exact NE.)

Interestingly, when we give up on the “well-supported” requirement for correlated equilibria, lots of other things become possible. Notably, all the players can play a with high probability 1−O(1/n), and this is what would start to happen if natural learning dynamics were applied to learn an equilibrium. Eventually, the dynamics should do something different; maybe converge to something in the region of the exact NE.