If you’re a physicist, mathematician or computer scientist and haven’t already seen MathOverflow then stop reading this post and go check it out. It is one of the best resources for research level math I have ever seen. It is absolutely shocking the speed and quality of responses to potentially very technical questions.

So, if you are still reading, I will presume you actually know the site. So why do I bring it up? Well, there is currently a proposal for a TheoryOverflow, aimed at Theoretical Computer Science, on the StackExchange site. Basically the way this works is that the people that produce the engine that powers the MathOverflow and StackOverflow websites are looking to produce similar sites in different areas. First an idea is proposed and fleshed out (Stage 1), once this is done it moves to a commitment stage where potential users are asked to commit to using the new site initially if it were made (Stage 2), either posting questions or answers. Finally it moves to a Beta (Stage 3). TheoryOverflow is currently in stage 2, and so needs support.

Rep, if you don’t know, is basically reputation, and so people who have contributed to other such sites carry more weight than users who haven’t. Different users have different amounts of rep depending on their level of contribution to StackOverflow and sister sites. Unfortunately more users seem to be necessary than usual, because most potential users committing to it seem to either be new or are coming from MathOverflow, and the StackExchange site doesn’t care about your MathOverflow rep (though it does about StackOverflow rep).

So basically, TheoryOverflow needs more support. If it turns out even a tiny fraction as useful as MathOverflow, then it will be a fantastic resource. So please help make it happen. You can sign up here.

Nice article (and a pretty cool photo) in The Record about my dear friend and collaborator Anne Broadbent.

If you have heard me talk in the last couple of months you may know that I have been working on trying to characterize the power of quantum interactive proofs with multiple provers. Well, I am delighted to say that our paper is finally on the arXiv here. I am quite chuffed with it since it is the first time I have been able to use an equation as the title of a paper, and is also the first time one of my results can be neatly captured by a single simple equation. Some how I feel it lends me more cred as a theorist!

Recently Jain, Ji, Upadhyay and Watrous proved the rather amazing result (here) that interactive proofs with quantum verifiers can only prove problems in PSPACE, and so are identical in power to interactive proofs with classical verifiers. Our result proves an equivalent statement for interactive proofs with more than one prover, basically showing that any interactive proof with potentially entangled (but non-communicating) provers can be simulated using only a classical verifier and some extra entanglement. The case for non-entangled provers had previously been proved by Kobayashi and Matsumoto (here).

Taken together these three results show something interesting, and quite counter intuitive: the availability of quantum verifiers does not change the power of any interactive proof system. Now, this result doesn’t necessarily hold when we fix the number of rounds (our MIP* protocols requires polynomially more rounds than than the equivalent QMIP protocol), but I find the symmetry in these three results pretty remarkable.

As Oded Regev pointed out to me on SciRate, some authors have used QMIP* to denote the quantum equivalent of MIP* and QMIP to denote the quantum equivalent of MIP. Although we were aware of this, there are at least two conflicting notations used, and we simply followed the convention used on the Complexity Zoo, to try to minimize confusion. One nice property of the notation Oded suggests, however, is that the three results mentioned above can be expressed as:

1. QIP=IP
2. QMIP=MIP
3. QMIP*=MIP*

Neat, no? So, how should I feel about QMA now?

If you know me personally or follow me on twitter then this may not be a big surprise, but I thought I would repeat the news here, since I am so happy. On the 2^nd of March I asked my wonderful girlfriend Amy to be my wife. I am delighted to say that she agreed!

We haven’t set a date yet, but we are planning to get married in summer 2011. I will post more plans as we make them, in the mean time if you are bored, you can check out our new wedding blog here.

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?