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.

I’ve just won $5 dollars form Scott Aaronson and Seth Lloyd, and I’m feeling pretty pleased about it. I’m splitting $15 dollars with Anne Broadbent and Elham Kashefi for a partial solution to the Aaronson $25 Challenge: Does BQP = IP_BQP. Dorit Aharonov, Michael Ben-Or and Elad Eban share $12 dollars for their independent work on interactive proofs. We don’t have a full solution to the problem yet, but we do know that an almost classical verifier can participate in an interactive proof of any problem in BQP. I’ll try to write a post on the problem soon.

The QIS workshop in D.C. should be over by now. Can anyone tell me how it went? I really wish I could have gone, but I have very limited travel funds and it was arranged very short notice. I know a few quantum bloggers went. Can anyone be persuaded to post a summary?

Let me explicitly warn you now, I am obviously not an economist and so the speculation contained in this post may be completely naive.

In the current climate, this is a question I find myself asking more and more often. Initially, prior to the recent global economic downturn I had been playing with the idea of whether it would be possible to apply fault-tolerance ideas to investments, but I never really reached any firm conclusions. Applying such ideas to an entire economy might be much easier, since you could consider substantial changes to the regulatory apparatus which would be impossible for a single investor.

So what do I mean by this? Well, basically one way to look at the economy is as a computation. Every trade, every bailout, every lay-off or expansion constitutes a step in the computation, essentially a logic gate. So what are we computing? Well, the unemployment level is clearly a function of birthrate, emigration, hires and fires/redundancies. The Dow-Jones is a function of the stock price of 30 blue chip companies, which are themselves dependant on recent trades.

It seems to me that bail-outs and interest rate adjustments can be viewed as a rather crude attempt at error correction. So we translate the processes which constitute the economy (financial, employment, policy, external events, etc.) into gates within a computation, we can start to bring computer science results to bare on the problem. One question we can ask is whether error-correction is sufficient to stop the computation going off-track. The resounding answer to this question appears to be “no”, given that the cause of the recent economic crisis traces back to sub-prime mortgages. Indeed this is what we would expect viewing the process as a computation. Trades in mortgage derivatives spread throughout the system, and so when people started defaulting on their mortgages, the impact was felt throughout the economy. This is exactly the situation fault-tolerance is designed to avoid.

In a fault-tolerant computation the computation is performed in such a way that an error in one area does not propogate throughout the system. We can certainly data mine past transactions to determine a noise model for the computation (coming from external factors and our inability to predict exactly what anyone is going to do in any given circumstance), and so should be able to determine what noise factors are correlated, and which are independant. As an example, the stock price of companies within the same sector will likely be correlated in their reaction to external events. This noise model is fundamentally important to designing fault-tolerant operations.

So how could we apply fault-tolerance to the economy? Well, first we need to identify the subspace we wish the computation to remain within. Now, our initial state must be within the stabilized subspace. This means we can’t really use fault-tolerance to maintain low unemployment and high stock prices, since that is not the regime we are currently in, but we can certainly design the system so that noise will not significantly raise or lower certain economic indicators we have decided to protect, allowing only intentional actions to manipulate these indicators. Faortunately, almost any indicator we can choose will depent on a range of factors, essentially acting as an error correction code. Now, unfortunately we don’t get to choose our encoding, but it is fortunate that a fairly decent one already exists due to the complexity of the economy.

So if we have an error correction encoding (we essentially want a form of self correction), what else do we need? Well, one thing we need to do is to formulate a set of fundamental operations which does not lead to correlation in noise. One way to do this is to impose strict rules on how investment can be made in such a way that not only do we require investment be spread across many sectors, but also that individual investors be required to invest in a sense independently. I know that this requires a huge regulatory aparatus, but if it could free us from the fear o economic downturn, it would surely be worth while. Now I suspect that my libertarian friends are going to find this a horrifying prospect, if we can identify a universal set of operations for computation of the factors individual investors care about, then we haven’t asked anyone to give up any freedom in their goals, we would only have required them to go about them in a much more responsible way. The end results should not actually be much different. The way things are at the moment, we are actively propogating risk within the economy and the financial markets, and it seems that this can be halted relatively easily.

So what would we need to do if we wanted to take a more rigorous look at this problem? Well, a few things we would need to determine:

1. What economic indicators do we really care about?
2. What constitutes a universal set of operations for what governments want to accomplish?
3. What constitutes a universal set of operatons for what investors want to accomplish?
4. What is a reasonable noise model? What’s correlated and what’s not?
5. How much this will piss off Peter?

Thoughts?

I was just watching some of the @Google talks, when I came across one given by Sean Carroll who is one of the bloggers at Cosmic Variance. The video seems to be new, but I can see no mention of it on CV. The talk basically is an overview of dark matter and dark energy. Anyway, I really enjoyed it, and the chances are that if you read this blog you may too.

Since I’m on the program committee for this workshop, I should probably give it a plug on my blog. It’s an interesting mixture of disciplines, so it won’t just be quantum loonies.

Event Title: Workshop on Logical Aspects of Fault Tolerance (LAFT)
co-located with LICS 2009.

Date: 08/15/2009

Location: University of California, Los Angeles

URL: www.aero.org/support/laft

Description:

We are soliciting papers on logical aspects of fault tolerance. The concept of “fault” underlies essentially all computational systems that have any goal. Loosely speaking, a fault is an unintended event that can have an unintended effect on the attainment of that goal. “Fault tolerance” is the term given to a system’s ability to cope in some way with a fault, either inherently or through design. Fault tolerance has been studied for its application to circuits, and then branching out to distributed systems and more recently to quantum computers, where the concern with fault tolerance is almost the paramount issue. The relevance to biological computation is also obvious. Papers must be concerned with the logic of fault tolerance, not simply fault tolerance.

IMPORTANT DATES:
Papers due: April 17, 2009
Notification: May 22, 2009
Final papers: July 10, 2009
Workshop: August 15, 2009

Please send all workshop correspondence, including submissions, to marcus [at] aero [dot] org