Thursday, October 15, 2015

Call for Nominations: EATCS FELLOWS 2016

European Association for Theoretical Computer Science (EATCS) Fellows 2016
  • VERY IMPORTANT: all nominees and nominators must be EATCS Members
  • Proposals for Fellow consideration in 2016 should be submitted by DECEMBER 31st, 2015 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, chair) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France)
- Dorothea Wagner (Karlsruhe, Germany)
- 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 2016 must be received by December 31, 2015.

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)

Saturday, August 29, 2015

advice for would-be PhD students

I recommend the article 10 steps to PhD failure in the Times Higher. The authors are based in Canada and are in the social sciences, but their list of 10 things to avoid, is something that would be useful to many prospective doctoral students I’ve come across. The most important ones, appropriately listed first, are
  • Stay at the same university
  • Do an unfunded PhD
  • Choose the coolest supervisor
In what follows, I’ll assume you have read the article, and I just add some more notes. That first item, “Stay at the same university” refers to the practice of doing the PhD at the same university where you did your previous degree(s). My take on this is slightly different from the authors of the article. It’s not so much that staying the same university is intrinsically a weakness, but it raises the concern that you may have started on a doctoral degree for the wrong reason, i.e. geographical inertia, rather than the right reason which is that the research topic is of consuming interest. At the point that a prospective student is applying for PhD places, it looks a bit weak to only apply at one’s current university; a student who is bent on doing research should communicate that by maximising his chances of getting to do research — i.e. apply more widely, rather than maximising his chances to continue to live in the same town.

Concerning the “coolest supervisor” point, similar to “same university”, it is not necessarily wrong to end up with the coolest supervisor, but there exists the risk that the coolest supervisor was chosen for the wrong reason (coolness) rather than the right reason (you have a good working relationship, and the supervisor is good at what he does). Of course, finding the right supervisor is a notoriously hard problem and is very hit-and-miss. The risk is best mitigated by applying at multiple institutions, which gives you the opportunity to go for interview and meet potential supervisors, which gives you the opportunity to see whether you have a rapport.

(added 2 days later:) Some follow-up: I followed the steps to PhD failure and came out with a doctorate, and an older article said to be “trending”: 10 truths a PhD supervisor will never tell you.

Sunday, July 05, 2015

Peyton fest

I write to thank the organisers of Peyton Young’s 70th birthday symposium, held in Oxford last week. The great thing about birthday symposia is that they are not rational in the economic sense (they do not make money) so they feel like taking a stand against the bean-counting mentality. Through celebrating the work of one of the research community’s well-known figures, we celebrate the community itself, and the intrinsic interest of the topic. Here’s a couple of thoughts on rationality. Vince Crawford’s talk made a point that explains one reason why game theory usually focuses on rational agents rather than boundedly-rational ones: I am tempted to call it the Anna Karenina principle: that rational agents are all alike, but every irrational agent is irrational in its own way. Hence, the study of irrational agents becomes diffuse, with a difficulty to reach agreement on what kind of irrationality to allow. (e.g.: I care about what values of ε one could compute ε-Nash equilibria in polynomial time, and one could argue endlessly about what constant value of ε might be considered acceptable. This is why a PTAS would be so nice.) Prior to hearing that point being made, when asked to explain why economists focus on rational agents, I’d note the basic requirement of economic mechanisms that they should function well in the presence of rational agents, and in general it’s too much to ask that they should perform well in the presence of irrational ones. The other item: in Peyton’s speech at the end, he considered possible future directions for game theory, and proposed that adaptability to changing conditions may become the new rationality: an agent should be judged on how well it handles change rather than whether it best-responds to a fixed environment.

group photo

and the programme

Friday, June 12, 2015

unimportant email

I’ve been getting quite a lot of journal spam recently. I wonder what sort of people would take the following seriously; it has an entertaining aspect (subject line: “Possible chance of publishing”).
Dear Dr. Paul Goldberg,

Greetings from International Journal of Innovative Research in Computer and Communication Engineering!

Hope this mail finds you in a jovial mood.

Assuming that you may have received our previous correspondence we are sending this as a polite reminder request to you. To know more about the journal, please visit here:

We would like to invite you to contribute a manuscript to be considered in the forthcoming issue of International Journal of Innovative Research in Computer and Communication Engineering (IJIRCCE).

(remainder not quoted)

“polite reminder”? I’m feeling more jovial by the second…

It reminds me of a fairly reliable rule about email, which is that there is an inverse relationship between the importance of a message, and the quantity of formatting (colours, fonts, links etc.) that it contains.

(added 16.5.15:) Another similar item of journal spam (subject “Publish your research”; includes request to be notified when you read the message):
Dear Dr. Paul Goldberg

Greetings from International Journal of Biomedical Data Mining!

Hope this mail finds you in a pink health!

We are enthralled to know about your scientific contribution in the area of Artificial Intelligence, Data mining and would like to invite you as a potential author.

(remainder not quoted)

(added 7.7.15:) The following comes from an address ending in, with a reply-to address of Subject is *Solids and *Structures(SAS):

Dear *NAME*,

Your paper, Revenue maximization in a Bayesian double auction market, draws our attention.


Solids and Structures(SAS) is an internationally refereed journal dedicated to publishing the latest advancements in solids and structures research.

World CatgetCITED
Academia.edupub zone
Submission deadline

July. 26, 2015

Tips: accepted paper which is submitted before the deadline can enjoy a discount on registration fee.

That last example uses the new-ish technique of making reference to one of the recipient’s papers, presumably to gain his attention. Shame about the salutation, Dear *NAME*.

Wednesday, April 29, 2015

tempted by a cut to 6k tuition fees?

I have as many ill-informed opinions as the next voter, but luckily the only ones I consider writing up here are the ones directly relevant to academia.

A well-publicised Labour manifesto policy is to cut tuition fees from 9k/year to 6k/year, and this is meant to be a positive selling-point of their package.  Much as I disliked the change to the current regime, I can’t get excited about this proposal. Thinking about why not:
  • A reduction of 3k is not a very big discount on 9k plus living expenses.
  • The 6k proposal lacks detail about the repayment terms and interest rates (I did read the relevant part of the manifesto). Thus, we’re being offered a pig in a poke.
  • There is no proposal to refund the students who have been required to take on 9k of debt per year. This shows a regrettable tolerance of unfairness to people who have ended up in greater debt due to sheer bad luck. The 6k tuition fee proposal is not so much about righting a wrong, as about a headline-grabbing policy proposal.
  • This article seems to be showing that the current fees have at least brought in more money to UK universities, which is being spent on students. This takes place at a time of considerable international competition between universities, and we cannot afford not to spend more money on facilities at universities.
  • While the current fees regime in unsustainable, we should welcome a transient period of stability (“meta-stability” for readers who know about Markov chain mixing…); I think we’re suffering from change-fatigue.
None of the above is supposed to be taken as supportive of the current 9k fees. I could actually feel supportive of this proposed cut to 6k, if it was presented as a step in the right direction; some kind of down-payment on the way to the abolition of fees. But that’s not how it’s being presented.

Added 16.10.15: THES article: Student voters had ‘less impact than expected’ on general election; sub-headline: Lack of enthusiasm for Labour £6K fees policy could have been factor, says Hepi report

Wednesday, April 01, 2015

Rating my co-authors

I feel like I’m something of a late-comer to the Rate My Co-author community (I include a link below, for completeness) and now feel like I should have joined earlier. It looks like one of these things whose user base reaches a critical mass, and then everyone has to join in. To be honest, I’m rather annoyed at how many of my co-authors seem to have claimed more than their fair share of the credit for various papers I worked with them on; now it seems I have to choose between making a counter-claim (and rely on Procaccia and Goldman’s fair division algorithms to moderate), or else enter into a costly dispute that may leave me worse off than if I just cave in and accept the lower share of credit. Their plan to integrate with Google scholar to produce the “world’s most accurate measure of an individual’s research contribution” is worrying. On the other hand, the fun aspect is seeing quite how many well-known papers seem to have dragged their authors into protracted disputes, to the extent that the authors end up with fewer “good co-author” points, than if only they had originally accepted a smaller share of the credit!

Anyway, the thing I like is the way you get to rate co-authors on about a dozen useful, but distinct skills. For example: Finding a fruitful line of research, Problem-solving, Being an optimist, Choosing a good venue, etc. There is clearly a big win to be had when it comes to team-building: we can now look up the skills of a potential research team, and check we’ve got everything covered. Previously I thought that Linkedin endorsements were the only available resource for this, but I admit to having been reluctant to endorsing my colleagues for (say) Latex skills, in case they take it the wrong way and demand endorsements for Algorithms, or Game theory.

Thursday, March 26, 2015

Tutorial talks, and a reminder that total search problems are not NP-complete

Here is a link to recordings of invited and tutorial talks at the recent STACS 2015 conference. (Slides are available here.) These recordings include my tutorial talk on algorithmic game theory, all 3 hours of it, which may possibly be of use to writers of articles with titles like The Top Ten Mistakes you make When Giving a Technical Talk.

Possibly the commonest mistake (other than dressing badly) is to assume too much knowledge on the part of the audience. This mistake wastes the opportunity for a “big win” in which you present some fact or result that most people in the room don’t already know, but which should by rights be ingrained in their DNA. I got to do that via presenting Megiddo’s 1988 result that NP total search problems cannot be NP-complete unless NP=co-NP. To be clear, an NP total search problem is one where every instance has an easy-to-check solution, for example FACTORING, where the output is a prime factorization of an input number, or NASH, where the output is a Nash equilibrium of a given bimatrix game. This is the reason why we don’t bother to look for an NP-hardness result for NASH, and have to use an obscure-looking complexity class like PPAD.

It's possible to write a convincing proof sketch as follows. Consider what would it would mean if an NP total search problem (like FACTORING) was NP-complete. There should then be a poly-time reduction from (say) SAT to FACTORING. That is, an algorithm A that can solve SAT efficiently, provided that it has access to an efficient solver for FACTORING. Now consider what happens when pass a non-satisfiable formula Φ to A. What you end up concluding is that any run of A must constitute a (short) certificate that Φ is not satisfiable, implying NP=co-NP. A will process Φ, from time to time constructing instances of FACTORING that it can solve “for free”. Since every such instance of FACTORING must have a solution, A cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance, so must run its course. If it ends without finding a satisfying assignment, there isn’t one.