I’m back from the FOCS conference in Atlanta, and since Lance has pointed out the lack of blog posts about it, I thought I would try to say something about it.

For those of you who don’t already know, FOCS is actually the IEEE Symposium on Foundations of Computer Science, and this year marks the 50th annual meeting. This was also my first time to attend FOCS, and it was a slightly odd experience. My background is in theoretical physics rather than theoretical computer science, so I am much more used to the physics model of conferences and publishing.

One thing I found particularly odd is that for such a prestigious conference with a rigorous review process they limited all the talks to 25 minutes including questions. Given the technical nature of many of the results this seems a little strange. Is there really a need to compress the conference into 3 days if it means having such little time to take in each of the results. This also seems to lead to a rather strange style of presenting, where some speakers seem to dive into the technical details without giving the intuition behind their approach. Maybe this is just a cultural difference between CS and physics, but I can’t help thinking that the compact time frame for talks really limited how much I actually took in. There were a lot of very interesting results, and I really wish I had had more time to process these before moving on to a new topic.

The other thing I found strange, being used to physics conferences, was the lack of a conference dinner. I usually enjoy conference dinners as they tend to be a great way to meet other people in the field. While there were lunches on two of the days, these really did seem quite cliquey and so I mostly ended up meeting people who were connected to one of the other quantum speakers (we had our own clique!).

So now I’ve brought up two things I didn’t like about the conference, perhaps I should focus on the things I really did enjoy: the talks. Keep in mind that I have a very different background to most of the attendants, so I am probably skipping over some other great talks. These are simply the ones that caught my imagination.

Day 0 of the conference was last Saturday. It wasn’t part of the conference proper, and was open to the public. There were a series of public talks to mark the 50th anniversary of FOCS and the 20th anniversary of the algorithms, combinatorics and optimization program at Georgia Tech. Even though I ended up staying in the Hotel Palomar (which I thoroughly recommend) right beside the auditorium it took me nearly an hour to find the right place. In retrospect, it shouldn’t have been hard to find at all, except that the map was somewhat inaccurate, and seemed to direct us to a building on the opposite side of the road.

There were four talks in total, from Richard Karp, Mihalis Yannakakis, Noga Alon and Manuel Blum. Unfortunately jet lag got the better of me, and I ended up missing the last talk. Of the first three, I particularly enjoyed Mihalis’s talk on equilibria. Why? Well it seems that many of the equilibria problems he was discussing are of a similar form to the the equations that arise in dealing with closed timelike curves. This probably shouldn’t be surprising, since Deutsch’s consistency condition is effectively just enforcing equilibrium, but none the less I found the connection fascinating. Actually throughout the conference, I found that quite a number of talks dealt with issues that also arise in physics.

Sunday marked the star of the conference, and also the start of parallel sessions. As a result, I was constantly having to decide which session I wanted to attend, and so could only see half of the talks. In the morning I attended session 1B (see the program here), and got a good sampling of talks on complexity. I’ve been interested in a (quantum) communications complexity question for some time, so I particularly enjoyed Paul Beame’s talk on multiparty communications complexity.

By far the highlight of the day for me, though, was session 2A, where we were introduced to the abstract tiling model model by David Doty, before Sandy Irani’s excellent talk on the connection between this problem and Hamiltonian problems in quantum complexity. I really found this session to be eye opening, as I hadn’t been aware of the abstract tiling model before, but it has really caught my interest. Sandy’s talk in particular caught my interest, and I will be reading their paper in detail once I can get my current teaching backlog out of the way.

The other talk that I greatly enjoyed was on polynomial identity testing given by Shubhangi Saraf (particularly the colourful combinatorics!). Unfortunately by this stage I was pretty worn out, and didn’t really take everything in. Another paper for the reading list.

The highlights of day 2 for me were talks by Alexander Sherstov on the intersection of half-spaces and by Vitaly Feldman on statistical query learning.

On Saturday myself and my co-author Elham had flipped a coin to decide who would give our talk, and I lost. On Monday evening we went out to my hotel to finish the slides and have a celebratory dinner to mark our first FOCS paper together. The Palomar, where I was saying, somehow seemed to be both cheaper than the conference hotel and much better. We sat beside a fire pit on the roof terrace, putting the last touches on the slides. Not a bad way to prepare for a talk!

Tuesday was the third and final day of the conference. The quantum session was in the morning, which unfortunately meant quite a low turnout. I have to say, I enjoyed all three of the other talks in the session. Our talk was first, at 9am, followed by André Chailloux talking about quantum coin flipping, then Sarvagya Upadhyay talking about quantum interactive proofs, and finally Ben Reichardt talking about quantum query complexity and span programs.

I found Sarvagya’s talk particularly interesting, but also kind of strange. In his talk he was showing that two message quantum interactive proofs are in PSPACE. This was certainly a major result and I was very interested to hear the details fo the proof. What was strange, however, was that I know the same authors have proved the much stronger result that QIP=IP or equivalently QIP=PSPACE. It is a little strange to sit through what you know to be a talk about a weaker result, when you know the speaker has the stronger result ready to go. Oh well!

Unfortunately, after our session I realised that we could prove another result about interactive proofs, and spent the rest of the day working through the details with Elham, and so missed the later talks.

Despite my reservations about the structure of the conference, I very much enjoyed my first FOCS experience, and I’m hoping that we’ll get the new results written up in time for STOC.

I’m now on twitter. It turns out to be a lot more interesting than I had been expecting, probably due to the relatively large number of QIPers/exQIPers (@dabacon, @mattleifer, @danbrowne77, @WaterlooIQC, @iqoqi, @coherence, @dwavesys, @rohde, @mickbremner, @michael_nielsen, @tobiasosborne and @seandbarrett).

No, not mine. My DPhil student Yuichiro Matsuzaki has just uploaded his first paper to the arxiv. It should appear in the quant-ph morning mailing. I might write something about it once it appears.

It seems that the UK government plans to limit freedom of expression for immigrants wishing to become citizens. The Guardian has the story. It seems if you voice opposition to government policy (and by this I mean the policy of the current party in power) you can be declined citizenship:

At the weekend stories attributed to government sources suggested that immigrants who took part in anti-war demonstrations could jeopardise their chances of qualifying for citizenship.

….

But, when it was pointed out that demonstrating was not illegal, Woolas suggested that an applicant could also lose points not just for breaking the law – but also for engaging in certain activities that were legal.

Sarah Montague, the presenter, asked: “Are you effectively saying to people who want to have a British passport, ‘You can have one, and when you’ve got one you can demonstrate as much as you like, but until then don’t'?”

Woolas replied: “In essence, yes. In essence we are saying that the test that applies to the citizen should be broader than the test that applies to the person who wants to be a citizen. I think that’s a fair point of view, to say that if you want to come to our country and settle, you should show that adherence.”

That’s Phil Woolas, the immigration minister. Well, Phil, allow me to acquaint you with Article 10 of the European Convention on Human Rights:

1. Everyone has the right to freedom of expression. this right shall include freedom to hold opinions and to receive and impart information and ideas without interference by public authority and regardless of frontiers. This article shall not prevent States from requiring the licensing of broadcasting, television or cinema enterprises.
2. The exercise of these freedoms, since it carries with it duties and responsibilities, may be subject to such formalities, conditions, restrictions or penalties as are prescribed by law and are necessary in a democratic society, in the interests of national security, territorial integrity or public safety, for the prevention of disorder or crime, for the protection of health or morals, for the protection of the reputation or the rights of others, for preventing the disclosure of information received in confidence, or for maintaining the authority and impartiality of the judiciary.

Maybe I’m missing something, but I don’t see any clauses where it says that it’s fine to limit these rights if the person is applying for citizenship.

This isn’t just a bad thing for immigrants: if new citizens are biased towards that agree with a particular political party due to requirements for citizenship, then it also skews the electorate. Allowing this decision to go through is essentially allowing a single political party to manipulate elections by biasing the selection of eligible voters.

Frankly I think Mr Woolas should consider resigning for conflating party interests (i.e. the Labour party’s interests) with the national good on such a massive and dangerous scale. But he won’t. It seems the last honourable man left the party in 2003.

But at least I have something to comfort myself with. Being Irish, I am an immigrant, but I am also entitled to vote in parliamentary elections. Oh, and since I am entitled to live and work in the UK, and my passport allows me to travel at least as easily as a UK one, I don’t really have to worry about his threats. Guess which party can’t count on my support?

I just noticed a friend’s status update questioning whether global warming has stopped since 1998. This shocked me a little, since it is a patently ridiculous claim, but apparently one being made by the group of nutjobs and the willingly ignorant who style themselves “global warming skeptics”. I think I prefer the term “reality denialists”. I’ve just done a quick search on Google News, amd this claim is everywhere. Fortunately most of these claims turn out to be in the Letters to the Editor section of newspapers, but it has managed to wiggle its way into articles too. A few years ago, in 2006, the Telegraph ran a story with the headline “There IS a problem with global warming… it stopped in 1998″. I guess this isn’t surprising, since it is after all the Telegraph, but even so I am shocked that such a claim is propogating.

So, I thought I should at least look at the data to see where the claim was coming from. This chart taken from Wikipedia seems to explain it all:

In 1998 there was an enormous spike in the average global temperature far exceeding the temperature in either 1997 or 1999-2001. As you can see, it is an outlying data point about as far from the 5-year average as any point on the graph. The problem with taking yearly temperatures is that the data is very noisy and the temperatures jump about quite a lot from year to year, obscuring the trend at least over short intervals. The running 5-year average makes it clear that the average temperature is increasing sharply. So where does this claim about no global warming since 1998 come from? Well, if you look at the temperature in 1998 and compare it to the average temperature from 1999 onwards then they are about equal. But this is complete nonsense since we’ve cherry picked the outlying 1998 data point as our starting position. If we start on the 5 year average, then we see a dramatic increase. In fact we could play the same game in reverse and say that the average global temperature has rocketed up since 1999 at almost double the actual rate. The claim that the average global temperature has not increased since 1998 is a flagrant abuse of statistics. It works simply by picking the hottest year on record as the starting point and then only considering a short time period so that the regression to the mean increase more or less cancels the increase in the average temperature. It’s a trick that preys on an ignorance of statistics. In five years the trick won’t work, because the increase in the 5-year average will have brought us far above the 1998 data point. So the claim is bullshit, pure and simple.

What is particularly incidious about this clasim is that it has almost certainly been composed deliberately to trick people. It often comes accompanied by an assertion that climate models fail to predict this halt to global warming, which is of course true. It’s true that none of the main climate models predict a halt or pause in global warming for the last decade, but that’s probably just as well, since there hasn’t been one. Should a climate model predict how people will abuse statistics? For me, predicting the climate change is enough and we can leave the precrime detection for the movies.

The list of accepted papers for FOCS has just been published. There appear to be 6 quantum related papers.

1. Two-message quantum interactive proofs are in PSPACE
   Rahul Jain, Sarvagya Upadhyay and John Watrous.
2. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
   Ben Reichardt.
3. Optimal quantum strong coin flipping
   André Chailloux and Iordanis Kerenidis.
4. The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
   Sandy Irani and Daniel Gottesman.
5. Universal Blind Quantum Computation
   Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.
6. A Probabilistic Inequality with Applications to Threshold Direct Product Theorems
   Falk Unger.

So what’s notable about this list (aside from the fact that I’m on it)? Take a look at the authors. Four of the six accepted papers have Waterloo affiliated authors. I count 7 current affiliations to either IQC or PI, out of 12 authors, and Elham has spent time at IQC in the past. If any proof were needed that IQC lives up to its promise its the above list. Try to imagine one institute producing 2/3 of the papers in Nature or Science. Hard, no?

WHERE IS MY VOTE

June 20, 2009

A week ago, Friday June 12, Ahmadinejad was declared the winner of the Iranian presidential election. Immediately after, all other candidates, Moussavi, Karroubi, and even the conservative Rezaei, disputed the official results. So did some people who started several demonstrations to express their anger. More news fueled the suspicion of fraud at an unprecendented scale. On Monday June 15, and to the amazement of the world, millions of people – of all ages, classes, and backgrounds – were in the streets of Tehran demanding another election in what was the biggest demonstration since the revolution in 1979. A week later, despite the threats and beatings issued and ordered by the government, millions of people are still demonstrating, and the movement is growing and spreading to other cities. Observers might find the situation confusing, since Iran has long been an isolated country and the everyday Iranian is unknown to the outside world. One cannot even prove that there was a fraud. There remains the fact that millions of people are protesting in the streets of Iran.

These are traditional, religious, modern, young, old, rich and poor, academics – some of them our colleagues – going out in the streets and risking their lives with a form of innocence in their aims and tactics. Some of them may stand on their roofs at night shouting “God is great” to keep the movement alive. They are braving the power because they insist that the Islamic republic is a republic.

The government is imposing a ban on the foreign press, shutting down all means of communication within their reach, arresting hundreds of prominent activists, politicians and religious figures opposing the results, and terrorising demonstrators. Every day fewer videos and reports escape from Iran. The state media is depicting the protests as incited by the West, accusing the movement of being a party of hooligans and traitors. After a week of uncertainty, the head of the state, Khamenei, just issued yesterday strong and explicit threats against participants in the protests and rallies.

This text is an urgent request to academics to fight the misrepresentation of this movement. This is not only about showing support to the courage and determination of people on the streets of Iran. It also means reaching for the many people in Iran who would like to participate but are frightened or know of the movement only through the state media. It means informing these people of the scale and nature of the movement, and thus widen its support within Iran. To all academics, please sign this appeal to support this movement in its call for a new election and oppose any violent intervention on protesters.

Dr. S. Aaronson (MIT) – Prof. S. Abramsky (University of Oxford) – Dr. R. Alleaume (Telecom ParisTech) – Prof. W. Arendt (University of Ulm) – Dr. E. Barker (University of Oxford) – Prof. S. M. Barnett (University of Strathclyde) – Dr. D. Browne (University College London) – Prof. P. Buneman (University of Edinburgh) – Prof. A. Cabello (Universidad de Sevilla) – Prof. T. Calarco (University of Ulm) – Prof. B. Chandrasekaran (Ohio State University) – Dr. B. Coecke (University of Oxford) – Prof. S. B. Cooper (University of Leeds) – Prof. D. W. Corne (Heriot-Watt University) – Dr. N. Datta (University of Cambridge) – Prof. V. Danos (University of Edinburgh) – Dr. J. Degorre (CNRS) – Dr. J. Desharnais (Universite Laval) – Prof. M. Dezani-Ciancaglini (Universita di Torino) – Prof. E. E. Doberkat (Technische Universitt Dortmund) – Dr. P. Dumais (Universite de Montreal) – Dr. K. Etessami (University of Edinburgh) – Dr. A. Feito (Imperial College London) – Prof. F. Ferreira (University of Edinburgh) – Prof. W. Fontana (Harvard University) – Prof. B. Foroughi (St. Francis Xavier University) – Dr. B. Farzad (Brock University) – Dr. J. Feret (INRIA) – Dr. J. Fitzsimons (University of Oxford) – Dr. D. Green (The City University of New York) – Dr. R. Harmer (CNRS) – Prof. J. M. Henderson (University of Edinburgh) – Prof. L. Hendren (McGill University) – Dr. M. Huth (Imperial College London) – Prof. H. J. Jensen (Imperial College London) – Dr. E. Kashefi (University of Edinburgh) – Dr. H. Koeppl (EPFL) – Dr. J. Krivine (IHES) – Prof. R. Laflamme (University of Waterloo) – Prof. B. Leimkuhler (University of Edinburgh) – Prof. N. Lutkenhaus (University of Waterloo) – Dr. D. Markham (CNRS) – Prof. H. Mairson (Brandeis University) – Prof. M. Mislove (Tulane University) – Prof. E. Mjolsness (University of California) – Prof. C. Moore (University of New Mexico) – Dr. M. Owari (Imperial College London) – Prof. C. Palamidessi (INRIA) – Prof. P. Panangaden (McGill University) – Prof. M. B. Plenio (Imperial College London) – Dr. O. Radulescu (University of Rennes 1) – Prof. Y. A. Ryan (University of Luxembourg) – Dr. A. Serafini (University College London) – Dr. P. Series (University of Edinburgh) – Dr. S. Severini (University of Waterloo) – Dr. M. P. da Silva (U. de Sherbrooke) – Prof. L. Smolin (Perimeter Institute) – Prof. F. Taddei (Universite Paris Descartes) – Prof. A. Tapp (Universite de Montreal) – Dr. L. Tortora de Falco (Universit Roma Tre) – Dr. D. Varacca (Universite Paris Diderot) – Dr. S. Virmani (University of Strathclyde) – Prof. P. Wadler (University of Edinburgh)

Tonight my heart hangs heavy. There can be little doubt now that the Iranian elections were rigged and that the population is being suppressed by a brutal dictatorship. It truly breaks my heart to see the violence dealt out on a people who want nothing more than for their voice to be heard. I don’t know who the woman in this photo is, but I am truly touched by her courage and her defiance. I wish I had half her courage.

There have been huge street protests and riots. Men with iron bars riding motorcycles are attacking protesters in the street, and attacking students in their dormitories. This cannot be aloud to stand. But there is hope. The Iranian people have not taken this matted lying down. At this point there seem only two possible outcomes: a massacre or the overthrow of a dictator. Tonight it seems the latter may be possible.

While I have never been to Iran, have only ever flown over it, while my personal beliefs are far different from many Iranians, and while I know little of the other candidates, I am human and I understand the drive for freedom from tyranny. I stand in solidarity with the people of Iran, for tonight everyone is Iranian.

So I guess I have blown any chance of ever getting security clearance for anything, and probably can’t go to Iran if the protesters fail, but that is meaningless. It is the people on the streets and in the universities that will suffer should the protests fail, which is why they must not fail. My heart is truely with the students in Tehran university tonight and throughout Iran.

The story seems to have been de-emphasised by many of the larger media organisations, so I will write this post in the hope that it reaches at least a few people.

The two best sources of information on this are liveblogs by Andrew Sullivan and at the Huffington Post. Also, tweets from those inside the protests: persiankiwi and Change_for_Iran, and hashtag #iranelections.

It seems that the government has been cutting off communication lines, and that twitter is one of the few ways for people to organize and get word out of the country. Access is being cut off, so the demonstrators are heavily reliant on outsiders setting up open proxies and relaying the details over twitter. I know many who read this will be tech savy, so I leave it to their judgement what they wish to do.

Let me close by saying that the people have spoken, and they have spoken for change:

I’ve just seen the future and it is wavy.

I’ve already applied for sandbox access, since it seems a much more natural solution for my Social Notebook project that the current cludge of Elgg and flash. I’ve been working on a tablet interface (in Silverlight of all things), but rather than adding it to the existing site, I think it is probably worth trying to turn the whole idea into a set of Wave extensions via robots and gadgets.

I’ve just received an email from Martin Plenio to tell me about a new initiative to exploit YouTube to promote science on the internet. Martin writes:

I am writing to you to bring to your attention some new tool that we (Daniel Burgarth and myself) have developed that has the aim of making science papers just a little more accessible. Its called Videoabstracts and consists of ‘homemade’ videos in which an author of the paper explains the key point of the paper in front of a whiteboard. The videos should not be longer than 5 minutes to force people to get to the point efficiently. We feel that these 5 minutes clarify the content and relevance of a paper much better than any abstract can do.

We have produced several examples that you may see on http://www.quantiki.org/video_abstracts. We did not strive for perfection as we feel that anybody should just be able to do these with a webcam and then upload them on QUANTIKI. The videos will then be stored on YouTube and at the same time a link will be created on the arXiv.

Viewers can leave comments on the content of the video and in that way stimulate discussions.

I’ve looked through the videoabstracts currently available (there are 11), and I can already see what a fantastic tool this can be. If only every arxiv paper had a five minute discussion of the key points it would save me a huge amount of time deciding what to read and what to skip. Scirate does a reasonable job of highlighting important papers, but its utility depends on how many people are actively citing papers. This new tool gives authors a way to introduce and promote their own work, in a very helpful and informative way. Given how opaque some papers can be, I certainly welcome the idea of a five minute run through from the authors. I’ll leave you with two video abstracts, one from Martin and one from Daniel to show how this works.