Friday, April 28, 2017

Wednesday, October 05, 2016

EATCS Fellows 2017 - Call for Nominations

The official call for nominations is at this URL at the European Association for Theoretical Computer Science (EATCS), below is a copy:
Deadline: December 31, 2016
  • VERY IMPORTANT: all nominees and nominators must be EATCS Members
  • Proposals for Fellow consideration in 2017 should be submitted by DECEMBER 31st, 2016 by email to the EATCS Secretary (secretary "at" eatcs "dot" org). 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, chair)
  • Anca Muscholl (Bordeaux, France)
  • Dorothea Wagner (Karlsruhe, Germany)
  • Roger Wattenhofer (ETH Zurich, Switzerland)

INSTRUCTIONS: A nomination should consist of details on the items 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 2016 must be received by December 31, 2016.

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): Name(s) Affiliation(s), email and postal address(es), phone number(s)

Please note: all nominees and nominators must be EATCS Members

Saturday, August 27, 2016

Graduate wage premium

I liked the Guardian article ‘Value for money’ can’t be the only measure of university, one reason being that it calls attention to Michael Oakshott’s 1950 essay The Idea of a University, which I now reckon should be read by every university student, or prospective student. No so much due to it being likely that they would buy into “the gift of an interval” as just that it presents a radically alternative viewpoint on the question of why people go to university; alternative, that is, to the current conventional wisdom that it’s about buying a ticket to a higher-paid job.

Graduates still benefit from a “wage premium”, despite increases in the proportion of people who go to university (article in FT, article in Guardian). This was found to be the case in a new report from the Institute for Fiscal Studies (link to press release) arguing that the continued wage premium is due to structural changes in organisations, or maybe due to increased demand (for graduates) increasing to meet the increased supply. The Guardian article notes that the IFS reckon that further increases in university take-up may reduce the graduate premium. I came up with the following observation (which doesn’t seem to have been suggested in the comments attached to the articles linked-to above). Suppose 99% of us went to university, then it seems likely that a “healthy” graduate premium would continue to exist. (The remaining 1% would be at risk of being seen to be missing some capability that nearly everyone has, and one would expect their average pay to be lower.) The point of that observation is to challenge the idea that we should care about the graduate premium.

Tuesday, June 28, 2016

Note on the EU referendum, ex post

The EU referendum has been interpreted as showing a nation divided by age (older people more likely to have voted Brexit), or possibly affluence, or alternatively geography (as in: Scotland and London more likely to have voted Remain). But plenty of older people voted Remain, likewise there was no clear consensus either way in any geographical region. Maybe we’re actually a nation divided by social networks: people seem to have voted the same way that “everyone” they knew voted. We all exist in social micro-environments, and in the case of academia, they are further subdivided into what might be called nano-environments. I may be biased towards the social-networks story, having dabbled in the associated theoretical problems that have been considered in the Computer Science theory literature. Perhaps the UK’s social network has not one, but two, giant components. If so, that has implications for social mobility. It may be felt that one of them is more effective than the other, when it comes to creating career opportunities for its members.

Sunday, June 19, 2016

Notes on the EU referendum

The June 2016 issue of the Oxfordshire Observer, a newsletter from the local Liberal Democrats, had the headline “Remain for prosperity”, and from the article: “Thousands of jobs in the county have been created or supported by EU funding. Oxfordshire receives millions of pounds of investment in innovation and research from the EU.” This helps to explain why most members of the academic community, myself included, intend to to vote to remain in the EU. I worry that the article is Oxford-centric and that all this “investment” is at the expense of other places. Now that council leaders of the main northern English cities have also come out in favour of remaining in the EU, that concern is alleviated.

Concerning Europe’s research funding, I have some sympathy with remarks made in Andre Geim’s Nobel Prize lecture, Random Walk to Graphene, which (as suggested by the title) is worth reading in full as a heartening reminder of the hit-and-miss nature of scientific advances. On pages 77 and 92, EPSRC’s responsive mode comes in for high praise while the EU Frameworks programme “can only be praised by Europhobes”.

EU membership is convenient when it comes to offering jobs and student places to other EU nationals. A downside is that we maybe don’t do enough in UK academia to nurture home-grown talent. According to these HESA figures, about 35-40% of UK-based academics and researchers in science and engineering are not UK nationals. It’s entertaining to imagine what would happen in the UK academic community (at least, some parts of it) if we were suddenly disallowed to appoint foreign candidates to academic posts. It might help the UCU’s claim that “Universities need to answer some hard questions about how they will continue to attract and retain the best talent when pay is being held down…”

Another argument for remaining in the EU is that the job market mobility may, over time, exert pressure to reverse the UK’s debt-based approach to student funding. That is, if it’s easy for someone to get a degree here and then go elsewhere to live and work, then the debt (repayable via UK taxes) doesn’t get repaid, and an incentive is in place for productive people to study in the UK but to move elsewhere.

For balance, here is the best article I have seen so far in support of voting to leave.

I wrote the above before finding this blog post of Tim Gowers in support of remaining, in which he compares leaving the EU to defecting in the Prisoner's Dilemma. It surely deserves a mention/link.

Thursday, February 04, 2016

Bristol Algorithms Days

A quick note of thanks to the organisers of Bristol Algorithms Days, a 2-day workshop (just ended) featuring talks on ongoing work on algorithms and proof techniques for analysing their properties. The event attracted quite a few colleagues from the UK and a surprising number of visitors from further afield. I got a useful introduction to some important lines of research that I’d been vaguely aware of, ones that deserve to be somewhat familiar to those of us in the algorithms community. A notable one is SETH-hardness, and 3SUM-hardness, and their usefulness for providing evidence that various polynomial-time algorithms cannot be improved on (e.g. the quadratic time taken by dynamic programming for problems like longest common subsequence, and computation of Frechet distance as well as other geometrical problems) (talk by Karl Bringmann). Another topic (talk by Iordanis Kerenidis): quantum algorithms that give exponential speedup for certain linear operations, and the applicability of these to machine learning; apparently there’s interest at Google and Microsoft in the potential applicability of such algorithms to their data. A talk by Alina Ene on computational learning problems that can be modelled as constrained submodular maximisation problems was interesting to me, having gotten somewhat familiar with submodular functions in economic-theory contexts. That list is non-exhaustive…

Thursday, January 28, 2016

go-playing AI

Back when I was a student I was a fairly enthusiastic Go player, and always liked the fact that it seemed to be resistant to efforts to make a strong go-playing computer program. (At any rate, it resisted my own effort to write a strong Go-playing program.) Having followed the progress of go-playing programs, of course I was interested in the success of the Google DeepMind program (articles in the BBC and Guardian) against Fan Hui, Europe’s top Go player. As noted in Neil Lawrence’s Guardian article, the DeepMind program doesn’t achieve the data efficiency of human players, so there is still work to do. And for those of us who like to imagine that Go is really supposed to be hard to program, there is a glimmer of hope: Previous Go-playing programs perform better against a human opponent during the first few games, and then the human opponent learns their weaknesses. Could Fan Hui eventually start winning, with a bit more practice?