{\huge Waves, Hazards, and Guesses}

Some matters of gravity in science \vspace{.1in}

Moshe Vardi is famous for many things, including his brilliant turn as the Editor-in-Chief of the Communications of the ACM. In the current issue he contributed an Editor's Letter titled ``The Moral Hazard of Complexity-Theoretic Assumptions.''

Today Ken and I want to comment on Moshe's piece and the larger issue of guesses and possible hazards in science.

Indeed, we wish to follow up our recent post on complexity theory's standing between ``magic'' and ``science'' by discussing how it compares to other sciences, in particular physics. Physics is an empirical science but guesses shape how theories are organized and how large experimental efforts are appropriated. We take a different tack from Lance Fortnow's response, which also has some notable comments.

As you probably know already, the big news in physics is that gravitational waves (GW) have now been directly detected. Such waves were first predicted by Albert Einstein's theory of General Relativity. And you probably also know the two big recent results in our field on which Moshe comments---we can just give the paper titles: ``Graph Isomorphism in Quasipolynomial Time'' and ``Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)."

Slides and Hazards

Moshe's point about graph isomorphism (GI) is that the ``slide'' from polynomial to quasipolynomial time takes us further away from the original idea of a benchmark for truly efficient algorithms. László Babai himself has been strong in saying that his algorithm does not compete with existing code that almost always solves GI supremely well in practice. Indeed he predicts that his methods cannot ever achieve comparable efficiency. We think of it as a leap in theory because among time bounds definable via $latex {+,*,\exp,\log}&fg=000000$ there is nothing between quasipolynomial and the neighborhood of singly exponential time. But thinking it a leap to being ``efficient'' in practice, Moshe says, is ``simply ignorant of the reality of algorithmic engineering.''

We demur from the GI result being an instance of Moshe's further point about assumptions because, on the face of it, it doesn't involve any assumptions. Babai's result is as direct as can be:

$latex \displaystyle \mathsf{GI \in DTIME}[n^{(\log n)^{O(1)}}].&fg=000000$

Make no mistake, the $latex {{\cal E}}&fg=000000$-result is big. Both it and the $latex {{\cal G}}&fg=000000$-results have attracted press coverage that hail them as of huge importance. Gravity waves have been searched for almost a century, while a proof that edit distance is quadratically hard has been searched for almost half a century. OK, ours is more like 40 years, but ours is a newer area. Perhaps like the rule that one dog year equals seven human years, we should get some scaling factor on our open problems.

The new $latex {{\cal G}}&fg=000000$-result came not without hazards. Two years ago, the BICEP2 team announced the signature of gravitational waves in polarization of the cosmic microwave background and much else that distinguished among theories of the Big Bang. That claim had to be withdrawn after they were found to have used an inadequate model of interstellar dust. We will first tell the story of the new $latex {{\cal G}}&fg=000000$-result to emphasize how it has dealt with hazards. Then we will review the $latex {{\cal E}}&fg=000000$-result and try to compare them. Not that there is any direct relationship between waves and edits, but what we are comparing is: How the different sciences view assumptions and open questions.

GW Backdrop

The first person to notice the gravitational-wave signal, Marco Drago, was nowhere near the Laser Interferometer Gravitational-Wave Observatory (LIGO) in Livingston, Louisiana, nor its twin in Hanford, Washington State. He got an e-mail alert in his office at the Max Planck Institute for Gravitational Physics in Hannover, Germany, just before noon last September 14th. The LIGOs had only recently been re-started after a five-year upgrade for an ``engineering run'' that was entering its final week. We posted about our friend John Sidles's involvement with the previous LIGO version.

The LIGO teams pioneered a policy designed to test the equipment's and human members' ability to discriminate signals and to forestall rose-tinted biases in data analysis. A few senior members are authorized sometimes to inject a false signal. Thus the signal could have been an unannounced fire drill---except that the blind-injector hadn't yet been brought back online. Drago and his postdoc colleague Andrew Lundgren called the facilities in the wee hours US time, but heard only from Livingston and that all was normal. Followups over the next few days ruled out all ``blind injection'' and other accidental causes. That the twins received highly similar signals about 7 milliseconds apart, as expected given its direction and lightspeed, ruled out local disturbances of the kind that often threw off the previous LIGO apparatus.

Ironically the last task over several weeks was to gather lots of ``nothing''---normal operating data so as to increase the confidence that this signal was special. This went on through early October until the confidence passed the ``Five Sigma'' threshold for discovery, which we once discussed in connection with the Higgs Boson. This explains why the $latex {5.1\sigma}&fg=000000$ figure in the paper is so close to the conventional value. A followup paper describes other aspects, implications, and insights.

Taking some time to read news reports and the papers has answered some other questions for us, besides why the reported confidence is so close to 5.0. It is still a marvel that the big event happened so soon after the machine was switched back on, still in a preliminary mode. How many comparably big events have been observed in the weeks since then? The answer is none, except one medium-size event on Columbus Day whose confidence currently stands at only 2.33. This is not out of line with expectations, especially while LIGO still has much scheduled downtime until reaching final sensitivity in 2021. The LIGOs were designed and built and upgraded according to a plausible range of guesses about the frequency of detectable events---previously said to range from one every two years to several hundred per year.

We venture a side question: Are there any implications for the string-theory hypothesis that space has at least six more dimensions rolled up on the Planck scale? Attempts have been made to detect them by testing the expected dropoff from Isaac Newton's strict inverse-square law of gravity at tiny distances. Since gravity is directly involved in the waveform, would gravitational-wave events be expected to show any distinctive second-order effects? We say this partly to highlight that whereas the BICEP2 experiment did aim to test and constrain other theories, the LIGO objective was as simple and direct and grounded as we can imagine. It is truly ``$latex {{\cal G}}&fg=000000$'' whereas the BICEP2 design strikes us as having more ``$latex {{\cal E}}&fg=000000$.''

Edit Distance Lower Bounds

The edit distance problem has been around for decades and asks for the distance between two strings of $latex {n}&fg=000000$ characters. The distance is defined as the fewest inserts or deletes that must be made to convert the strings into the same string. It has been discovered many times, independently, that there is a simple dynamic programming algorithm that can do this in time quadratic in $latex {n}&fg=000000$. While there is a way to shave a tiny bit off this time, no algorithm has ever been found that can do this computation in time $latex {n^{2-\epsilon}}&fg=000000$ for some $latex {\epsilon>0}&fg=000000$.

The $latex {E}&fg=000000$-result of Arturs Backurs and Piotr Indyk shows that this is impossible provided we assume that the hypothesis SETH is true. Moshe says this:

What is SETH? The conventional wisdom is that P is different from NP. Thus, this is now taken as a standard assumption, even though the belief in it is mostly built around the questionable identification of P with efficiently solvable. In some cases, however, the P $latex {\neq}&fg=000000$ NP assumption is not strong enough. The Strong Exponential-Time Hypothesis (SETH) is a stronger assumption that asserts that Boolean Satisfiability (SAT) cannot be solved in strongly sub-exponential time (see the Backurs-Indyk paper for a precise definition).

Proving that SETH implies that edit distance requires quadratic time is already a very nice result. But the title of the paper implies one should not expect SETH to be false, which is the way the result was broadly interpreted. But SETH is a much stronger assumption than the P $latex {\neq}&fg=000000$ NP assumption. The evidence for this assumption is that so far no one has been able to come up with a strongly subexponential algorithm for SAT. But most progress in complexity theory over the past 40 years has been through the discovery of clever new algorithms, such as Khachian's Ellipsoid Algorithm for linear programming, Shor's quantum poly-time algorithm for factoring, and now Babai's quasi-polytime algorithm for graph isomorphism. If I had to bet, I would bet on further progress in improved upper bounds than on progress in improved lower bounds.

Essentially, Moshe is saying that proving a lower bound based on a very very strong hypothesis may be interesting and clever, but it does not raise his belief in the inherent difficulty of the edit distance problem. The issue is that SETH is just too powerful an assumption.

The authors have posted a reply to Moshe's comment here. They say:

Dr. Vardi is critical of the title of our paper: "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)." I can only say that, given that we are stating the assumption explicitly in the title, in the abstract, in the introduction, and in the main body of the paper, I believe the title and the paper accurately represents its contribution.

Dr. Vardi is critical of the validity of SETH as a hardness assumption: this question is indeed a subject of a robust discussion and investigation. The best guess of mine and of most of the people I discussed this with is that the assumption is true. However, this is far from a universal opinion. Quantifying the level of support for this conjecture would be an interesting project, perhaps along the lines of similar efforts concerning the P vs. NP conjecture---see this. In any case, it is crucial to strengthen the framework by relying on weaker assumptions, or replacing one-way reductions with equivalences; both are subjects of ongoing research. However, even the existing developments have already led to concrete benefits. For example, failed attempts to prove conditional hardness of certain problems have led to better algorithms for those tasks.

Compare

We promised to say something about how physics and complexity approach open questions. And we shall.

Ken and I note that there are fundamental differences in how the two fields operate. These are differences that are fundamental, since of course the work on $latex {{\cal G}}&fg=000000$ used a vastly experimental pair of expensive machines, and the work on $latex {{\cal E}}&fg=000000$ was the direct work of two authors. Of course the latter built on work done previously in complexity theory by others, but needed no experimental machines.

No we are interested in how the guesses were made. In physics the reason there was such belief that gravity waves would exist is that they were predicted by General Relativity (GR). In complexity theory the lower bound on edit distance is predicted by SETH. We align with Moshe and point out the vast difference for evidence for GR vs SETH.

• GR is likely to be true because it has predicted many unusual effects, which have all been confirmed. This gives one tremendous confidence. Note, if gravity waves were proved not to exist, then GR would have to be replaced.
• SETH is just as likely to be true as false in our opinion. The authors suggest talking a poll of complexity theory experts, but that is vastly different from saying that SETH has already predicted facts that have been confirmed.

It may seem silly that we are entertaining doubt of GR but in this particular area so did Einstein: he thought their faintness would escape detection and then wrote a paper removing GWs as a prediction of GR---until a math error was found in the draft of that paper. We must add a strong statement that we are impressed with the $latex {{\cal E}}&fg=000000$ result. It is a beautiful piece of work. But to say that it ``proves'' or resolves a 40 year old problem is way over-reaching. Perhaps we can view it as a kind of prediction:

No $latex {n^{2-\epsilon}}&fg=000000$-time algorithms will ever be found for Edit Distance.

Complexity theory is capable of both proving and falsifying such predictions, but it is at best unclear whether it is in any comparable sense able to empirically test them.

Open Problems

What do you think about SETH? Is it true? Or not? How does the framework of such hypotheses stand with regard to the sciences?