A recent post on this blog concerned the posting of our paper MIP*=RE on the arXiv and gave a personal history of the the sequence of works that led to the result. Quite unfortunately (dramatically?) a few weeks after initial posting of the paper (and the blog post) John Wright discovered an important error in the proof of a key result in this sequence: my paper Three-player entangled XOR games are NP-hard to approximate, published in 2016 in a special issue of the SIAM journal on computing dedicated to selected papers from the FOCS’13 conference. While I did not mention this paper directly in the previous blog post, its main result, a proof of soundness of the Raz-Safra low-degree test against entangled-player strategies, is a key ingredient in the proof of the quantum low-degree test, itself a key ingredient in the MIP*=RE paper. (Strictly speaking the latter paper relies on an extension of my result to two-player games obtained in a follow-up with Natarajan. Since that paper re-used the flawed part of my earlier analysis in a black-box manner it is similarly impacted.) So then…?
I’ll start with the science. The result MIP*=RE, to the best of our knowledge, remains correct. In order to remove the dependence of the proof on the flawed paper we extended the soundness analysis of Babai, Fortnow and Lund (BFL)’s multilinearity test against entangled provers from my paper with Ito to the case of multivariate polynomials of low individual degree. (This extension, for the case of classical provers, is already mentioned in the BFL paper.) We just posted a self-contained analysis of that test on the arXiv here and updated the MIP*=RE paper to account for the replacement (see v2.). The latter paper is currently under review; on this I will simply say that, as for all mathematical works, it is advised to wait until the outcome of the refereeing process is complete before declaring confidence in the validity of the result. For a more in-depth description of the changes made I refer to the introduction of the new paper.
Our analysis of the “low individual-degree test” mentioned in the preceding paragraph can be used to recover the main result of my SICOMP’16 paper in a weakened form. Since the proof is different and does not directly fix the error I have decided to withdraw the paper from SICOMP. For more details on the error itself and consequences to other works, such as the quantum low-degree test and the quantum games PCP, I refer to the short note I wrote to accompany the withdrawal of the paper. The one-sentence summary is that essentially all subsequent results expressed in terms of “high” complexity classes such as QMA-EXP, NEEXP, etc., still hold, while “scaled-down” results on the hardness of entangled games can only be recovered by allowing a substantial weakening of parameters. In particular, the quantum low-degree test holds in its scaled-up version (testing exp(n) EPR pairs using poly(n) resources), but the scaled-down version requires polylog(n) communication to test n EPR pairs, instead of O(log n) as claimed.
In addition to notifying researchers in the area of the bug, my goal in writing this blog post is to help me exorcise the demon of having a large mistake in one of my papers. In doing so I was inspired by Scott Aaronson’s blog post on a similar topic. (I’ll admit that even just linking explicitly to his post helps reassure myself, a power which I believe was one of Scott’s aims in writing the post. So, thanks Scott, and allow me to pass it on!) The faulty paper is not based on a minor back-of-the-envelope observation; in fact it is one that I was quite proud of. The mistake in it is not small either; it’s a mistake that I cannot find any excuse for having made. Yet here I am: after having spent the past 6 months trying to find an alternative proof, I now strongly believe that the problem cannot be solved using the kind of techniques that I had imagined could do so. Whether the theorem statement is true or not, I don’t know; but at the moment I am unable to prove it. I have to accept that there is a bug.
As painful as it is I realize that I am writing this post from a relatively comfortable position. Who knows if I would have been able to do the same had we not been able to recover a full proof of MIP*=RE. Moreover, after having banged my head against the problem for 6 months straight (COVID helping, walls were never far) I am now able to see my failure in a more positive light: the story I told in the previous blog post is not yet closed; there is an open challenge for me to solve. It is a very personal challenge; having spent the past 6 months delineating it I have accumulated sufficient grounds on which to believe that it is an interesting one. I feel grateful for this.
Getting there wasn’t easy. So, even though I am writing from a place of comfort, I want to share the pain that the whole adventure has caused me. This simple acknowledgment is especially directed at younger readers: so that when it happens to you, you will remember this post and know that you’re not the only one. That it happens to others as well and that it is possible to face, accept, and move away from such errors. Of course you will try to fix it first. Here are some quick tips. While banging your head on the problem, make sure that your understanding increases every day. To start with, do you really understand why there is a mistake? Of course some step doesn’t go through, but what is the simplest form of the incriminated statement that fails? Can you write it down? Can you formulate and prove a weaker form of it? Probe the issue with examples. Try to isolate it as much as you can: take it outside of the paper and formulate an entirely self-contained version of it, stripped of all the baggage. Place it in as many different contexts that you can think of: do you still believe it, does it stand on its own? Again, make sure that you learn. Even if you’re not able to fix the claim, are you exploring a new technique, discovering a new perspective? If it didn’t work yesterday it probably won’t work today either: make sure that you always find something new to inject. When you can no longer do this, it is time to stop. So make sure to set yourself some near-term (how much to think about this on any given day) and long-term (when to admit defeat) limits. Always remember that problems are much more often solved in the shower or while walking the dog than at the desk. Finally, be ready to move on. Realize that as bad as it may seem to you, there are more important things in life. You can’t reduce yourself to this one problem: you’ll be stronger for accepting what happened than trying to bury it at all costs. If you don’t see this by yourself, try to talk about it. Explain the situation you’re in to your close non-academia friends, to your parents; practice on your pet first if it helps. You will realize, as I eventually did (although it took quite a while) that it is ok.
After the scientific and the personal aspects, let me end with the sociological. This is a semi-tangent but it is a good opportunity to discuss a topic that we scientists, possibly even more so us working in the “hard sciences” (as the French call “proof-based” disciplines), are insufficiently sensitized to. This is the topic of how science is made, and what is the reality of this “absolute truth” that we claim to discover and establish in our mathematical results.
My paper was posted on arXiv in 2013, it was accepted to the FOCS conference and published in its proceedings the same year, and it appeared in the journal SICOMP in 2016. Both publications were refereed. Since its posting the paper has been cited 47 times (google scholar) and its main result is used in an essential way in at least half a dozen papers (my best guess). 7 years later a big hole has been found in the proof. How did the “truth value of my result evolve in the process? Was it always wrong or was there a time where it had truth, in whatever appropriate sense of the word?
I realize that these questions can be given trivial answers—I know what is an axiom and what is a proof system. Yet I am trying to push myself, and my reader, to look a little deeper. An analogy might help. The situation brought to mind a book by French philosopher of science Bruno Latour, called (in its English translation) Laboratory Life: The Construction of Scientific Facts. This is a wonderful book, which goes well beyond the classic misconceptions from Popper or even Kuhn; it should be mandatory reading for every scientist. In one of the early chapters of the book Latour makes a detailed study of how subsequent citations can collectively enshrine an initial claim based entirely on the citer’s conscious or unconscious biases in making use of the citation (i.e. in complete independence from any ground “truth” or “importance” of the cited work). An entertaining example of this can be found in this article, which dissects the claim that “The myth from the 1930s that spinach is a rich source of iron was due to misleading information in the original publication: a malpositioned decimal point gave a 10-fold overestimate of iron content.” The example, pursued in great depth in the article, shows very well how one citation at a time the (spoiler: unjustified) claim is given more and more credibility until it eventually becomes a fact: from initial citations written in a tentative tone “according to Z, it could be that…” to more assertive citations “Z has shown that” by more and more well-known researchers in highly-read journals to pure fact (citation above). I highly recommend the article!
It is easy to dismiss this story as being the result of “sloppy” authors misrepresenting a “soft” claim whose truth value is not well-determined in the first place, being a statement about the world rather than about some hypothetical mathematical universe. Yet I believe that it is worth taking the time to examine with an open mind what exactly, if anything, distinguishes a claim about the iron content of spinach from the main “theorem” of my paper. From its initial posting on the arXiv to its presentation in a conference and its journal publication to the multiple citations it received through its use in subsequent works, and including multiple other considerations such as my own credibility (itself the result of so many other considerations) and the results base “believability”, when was the logical statement itself evaluated? Does it matter? Did the unchallenged existence of the result for 7 years impact the course of science? Or was it a mistake that was bound to be discovered and has no lasting consequences?
These are questions for the reader, that can be (and are probably better) asked in other contexts than the limited one of my result. Indeed there is a much broader point to all this, that I only meant to raise in an indirect manner. It is impossible to disregard the fact that our scientific work is grounded in cultural and societal effects, but we may disagree on the impact that this grounding has. We owe it to ourselves and to our readers (broadly interpreted—from colleagues to funding agencies to the broader public) to refuse to hide behind the thin veil of “hard science”, mathematics or logic, and educate ourselves to what it is that we really are doing.