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?

Friday, January 01, 2016

problems with blogs

I just read this article in the Guardian: Iran’s blogfather: Facebook, Instagram and Twitter are killing the web. Iran’s “blogfather” Hossein Derakhshan describes an Internet Rip-van-winkle experience of being released from prison after about 7 years: he went to prison in 2008 during the heyday of blogs, and emerged to find a world of Facebook, Instagram, and apps. He seems disappointed by the transformation, for reasons I sympathise with. Then again, Mr. Derakhshan may end up learning to love modern social media.

I remember blogs. One difference they had from Facebook and other social media was they felt like a tool rather than a toy, something you can hurt yourself on. In the worst case, they get you murdered or imprisoned, and even in western democracies they could get you into trouble. On the other hand, the way Facebook works is that if you write anything remotely controversial, it won’t attract censure or ridicule, but will just be ignored completely; probably the system tactfully fails to show your contribution to anyone, or makes a potential reader scroll through 20 pages of photos of cats/children/cookery before finding it. The other big problem with blogs — the main reason why modern social media killed them off — is the cognitive burden they placed on both reader and writer. The blogger had to exercise creativity and effort in order to verbally articulate his subjective view of (some aspect of) the world; a lot of tedious word-smithing went into the task of presenting a line of thought for the reader. You had to have the mentality of one of those guys who spend all their time tinkering with some obsolete car, instead of replacing it with a new model that’s blissfully free of any user-serviceable parts. It’s even worse for the reader, who is lumbered with the task of figuring out the writer’s emotional state, and whether he (the writer) really means what writes, or if he’s joking. Contrast that with modern social media, where you just shoot off a photo and upload it, with minimal comment attached. For the coming year, I look forward to a sighting of Mr. Derakhshan’s cat.

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*.