Some matters of gravity in science

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 reader 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 but still represents that idea in news coverage. 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 ${+,*,\exp,\log}$ there is nothing between the neighborhoods of quasipolynomial and 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:

$\displaystyle \mathsf{GI \in DTIME}[n^{(\log n)^{O(1)}}].$

In that respect it is like the GW result. Let us collectively call results of that kind “${{\cal G}}$-results,” G for “ground.” And let us call the conditioned-on-SETH kind “${{\cal E}}$-results”—well we chose E for “Edit Distance” but it can mean extrapolated, picking up the general sense in which Wikipedia says extrapolation carries “a higher risk of producing meaningless results.” Of course our post appearing the same week as Moshe’s letter raised this about much of crypto, even going further about grounds to doubt the results being factually meaningful.

Make no mistake, the ${{\cal E}}$-result is big. Both it and the ${{\cal G}}$-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 ${{\cal G}}$-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 ${{\cal G}}$-result to emphasize how it has dealt with hazards. Then we will review the ${{\cal E}}$-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 his time 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, and we are even more awed by LIGO’s use of quantum optics to make distinctions on scales a fraction of the width of a proton, let alone an atom.

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 ${5.1\sigma}$ 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 “${{\cal G}}$” whereas the BICEP2 design strikes us as having more “${{\cal E}}$.”

## Edit Distance Lower Bounds

The edit distance problem has been around for decades and asks for the distance between two strings of ${n}$ 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 ${n}$. 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 ${n^{2-\epsilon}}$ for some ${\epsilon>0}$.

The ${E}$-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 ${\neq}$ 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 and 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 ${\neq}$ 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 letter in comments there and also 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 ${{\cal G}}$ used a vastly experimental pair of expensive machines, and the work on ${{\cal E}}$ 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 odd that we are entertaining doubt of GR but in this particular area so did Einstein: he thought the faintness of a spread-out GW by the time it reaches us would make it incapable of detection and then wrote a paper removing GWs as a prediction of GR—until a math error was found in it. Note, this was in 1936 when GR was fairly well established.

We must add a strong statement that we are impressed with the ${{\cal E}}$ 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 ${O(n^{2-\epsilon})}$-time algorithm 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?

1. February 16, 2016 1:41 am

For what it’s worth, here’s an old talk by Ryan Williams which also discusses a number of results of the form “One cannot solve problem X faster than the currently known best algorithm unless SETH is false”, but with the opposite framing of the Backurs and Indyk paper — i.e., presenting this as evidence against SETH rather than for the optimality of existing algorithms.

2. February 16, 2016 4:03 am

The edit distance result is a very nice one. I still find the authors a bit of bad faith in their reply to Moshe Vardi: They pretend not to see the difference between their title and “SETH implies that Edit Distance Cannot Be Computed in Strongly Subquadratic Time”, or one could also have the same title as theirs without the parenthesis. The message would be quite different. Actually, I don’t find that their title is bad/misleading/etc. They can well say that they are convinced that SETH is true, and that this is a message they want their title to convey. Only their reply saying that their formulation does not make a real difference is of bad faith…

3. February 16, 2016 7:36 am

but now it’s come to distances and both of us must try

I do see that both problems have to do with metrics, and I know that guessing is the work of Aristotle’s apagoge, also known as abductive inference, a mode of reasoning for which Peirce guessed we have a guessing instinct, and yet AI for all its acronymic inclusion has yet to bring abduction within the fold of algorithmic or even artful intelligence.

4. February 16, 2016 9:00 am

Analogies between physics and computing, or mathematics, or inquiry in general, recently arose on MWA, and there was a lot about shifting and sliding and slipping there, too. It all went a bit too fast for me, but here is one insertion point where I thought for a moment I almost had a clue —

February 16, 2016 11:36 am

Are there many other branches of math where assumptions are used in place of axioms? Complexity theory aims at building a science out of an art, though a systematic replacement of action by understanding can’t be achieved without gaps. As is well known, in theory there’s no difference between theory and practice but, in practice, there is.

February 17, 2016 10:48 am

The Riemann Hypothesis is widely used in this manner. See, e.g. this mathoverflow question: http://mathoverflow.net/q/17209

February 17, 2016 7:12 pm

Right, I was forgetting the Riemann Hypothesis. It’s an interesting phenomenon that sometimes, when things are too hard to prove they end up being used as axioms. Quite possibly, it’s their wide usability as axioms that makes them so hard too prove – because they have too many interesting consequences.

February 19, 2016 10:30 am

Pretty much all of mathematics is based (to some extent) on the assumption that ZFC is consistent. This doesn’t mean that a proof that ZFC is inconsistent would immediately destroy all of mathematics, but it would mean that mathematicians would have to replace ZFC with some other theory which would be just as impossible to prove to be consistent.

February 19, 2016 6:39 pm

Interesting point of view. ZFC is a good theory because it’s hard to prove bad. In this sense, ZFC itself would be a subset of complexity theory. But the main difference with P?NP lies in the symmetry: it’s either P=NP or P!=NP that’s too hard to prove but we don’t know which. Also, it might be very hard to find a counterexample to RH – just as hard as to prove RH.

February 24, 2016 6:52 pm

By the way, I wonder if the hardness of proving a conjecture has anything to do with the probability of raising a contradiction in PA. Maybe a proof of P!=NP could be turned into an algorithm that solved SAT in polynomial time, and maybe a proof of RH would allow you to exhibit a counterexample to RH. So we’d have a new kind of unprovable proposition: if it can be proved, then PA is inconsistent (just like the consistency of PA itself). I mean, complexity is perhaps a mere protecting mechanism against inconsistency!

6. February 16, 2016 1:24 pm

Aristotle’s apagoge, variously translated as abduction, reduction, or retroduction, is a form of reasoning common to two sorts of situations: (1) that by which a phenomenon (a fact to grasp) is factored through an explanatory hypothesis, or (2) that by which a problem (a fact to make) is factored through an intermediate construction. He gives one example of each type in Prior Analytics 2.25. I give some discussion here —

February 16, 2016 3:16 pm

Recent work by Abboud, Hansen, Vassievska Williams, and Williams shows that similar results holds for weaker assumptions than SETH, namely SETH for SAT on sublinear depth circuits, rather than for CNF formulas. I don’t know of any upper bound that beats 2^n even by a tiny bit for such circuits; it makes this weaker SETH even more plausible.

February 16, 2016 7:36 pm

> We think of it as a leap in theory because among time bounds definable via {+,*,\exp,\log} there is nothing between quasipolynomial and the neighborhood of singly exponential time.

Isn’t exp(\log(n)^\log\log(n)) strictly in-between quasipoly and exponential time, in contrast to your claim there is nothing in between?

• February 16, 2016 9:00 pm

Nice keeping us technically honest, thanks. Rearranged the sentence to fix it.

February 17, 2016 10:47 am

@Serge The Riemann Hypothesis is widely used in this manner. See, e.g. this mathoverflow question: http://mathoverflow.net/q/17209

10. February 20, 2016 2:27 pm

At least one concrete prediction of SETH has been verified. Mihai Patascu and I showed (in SODA 2010) that SETH implies that the number-on-forehead communication complexity of 3-party set disjointness is Omega(n). This lower bound was later proved by Rao and Yehudayoff in CCC 2015. So this is a concrete “prediction” about the status of an open problem that was later verified.

In fact the result in the SODA 2010 paper predicts that the nondeterministic communication complexity is also Omega(n), which as far as I know has not yet been proved.

11. February 21, 2016 10:15 am

The thing about edit distance is that if the distance is beyond some amount, (more in terms of a simple description complexity than actual distance), it’s probably not relevant in all of the contexts I know that use edit distance. In all of those contexts, the cases I care about can be solved in linear or nlogn time. In some sense, if it starts taking longer than that, I almost just want it to return “Not even close”, instead of spending ages matching arbitrary unrelated things that just happen to be the same.

• February 21, 2016 1:08 pm

Ryan, thanks—this also reminds me of Scott Aaronson’s post about evidence from P != NP.
Neil, interesting—I wonder if there is a theory about cases solvable in (quasi-)linear time, or about the efficacy of linear-time approximations such as we discussed in our memorial for Alberto Apostolico.

• February 21, 2016 10:44 pm

For a number of different problems, it’d be interesting to have a list of those sorts of common, relatively easy cases and approaches to solve them.

For finding the edit distance when it’s small, you can view the problem as finding the shortest path from one corner of an implicit n by n grid to the opposite corner, where there are implicit diagonal edges added corresponding with every individual match. Since there’s some small sequence of edits to map between them, there’s some path where almost everything matches, i.e. you can cut across the diagonal of almost every cell, in which case the A* algorithm avoids searching almost all of the grid. I’m pretty sure it ends up being linear time in the string size if the edit distance is bounded by a constant. It’s still n^2 in the worst case of two very different strings.

I’m curious if it can be easily extended to the case where the edit distance is large, but where there are large blocks that are entirely the same and large blocks that are entirely edited, and a constant number of blocks. I’m sure there’s been tons of experimental research into that case for code diffing, though they’re probably researching fancier stuff than just edit distance for it.

12. March 4, 2016 1:21 pm

Moshe is brilliant, a great high profile advocate/ spokesman for the field (esp his recent musings on AI/ robotics) but his editorial on edit distance seemed like hairsplitting to me and not quite enough to deserve an entire editorial. why not just write an unequivocal editorial on what a breakthru it is/was and note some quibbles with technicalities in the middle or end? popular science writing is always full of approximations and scientists are ever quibbling over the correct terminology. one wonders if a scientist would even be capable of writing a headline. (because it would never be technically/ strictly correct and free of qualifiers.) more commentary on historic backurs/ indyk result… and feel it was a big deal for the the emerging field of “fine grained complexity” and expect other results in this vein to follow. (hi RW!) 😀