The tail was named somewhere else

A search for a mountain-valley labelling of the rhombille tessellation patch costs eighty-four steps on its best run and does not finish inside twenty thousand on two runs in five. Nothing changes between the runs except the order the letters are tried in. And the right response to that spread is not patience: stopping every attempt after a hundred steps and starting again is thirty-two times cheaper than allowing each one twenty thousand.

Every part of that was known before anybody pointed a search at a crease pattern.

What was found, and where #

Three results sit behind the measurement, and they belong to the study of combinatorial search rather than to folding.

The first is the shape of the distribution. A randomised backtracking search on a constraint problem does not have a running time so much as a spread, and the spread has a long tail: most runs are cheap, a minority are enormously expensive, and the mean is dominated by runs that have not happened. Carla Gomes, Bart Selman and Nuno Crato described this in 1997, measuring runtimes of randomised backtrack search on constraint satisfaction and satisfiability instances and finding distributions whose tails fall off far more slowly than any exponential.

The second is the cure. If the distribution has a long tail, an attempt that has run a long time is not close to finishing; it is evidence of a bad early decision. Gomes, Selman and Henry Kautz turned that into a method in 1998 — rapid randomised restarts — and reported order-of-magnitude speed-ups on problems where a single run would not terminate.

The third is older and more general. Michael Luby, Alistair Sinclair and David Zuckerman worked out in 1993 what the optimal restart strategy is for a Las Vegas algorithm — one that always returns a correct answer and takes a random time to do it — including the case where the distribution is unknown, and gave a universal schedule that is within a logarithmic factor of the best fixed cutoff.

That is the whole of the theory this collection’s restart curve rests on. None of it is about paper.

It is worth noting what the three have in common, since it is not a shared subject. All three are about a procedure rather than about the objects a procedure is run on, which is why they transfer at all: a result about how a randomised backtracking search behaves applies wherever there is a randomised backtracking search, and the study of folding acquired one only when this collection built it. The hardness of deciding flat-foldability is the opposite kind of import — a result about the problem, which had to be proved for this problem specifically — and it took a reduction to establish rather than a recognition.

What transfers #

The arithmetic transfers exactly, because it never mentions the problem.

Attempts are independent if the only thing that varies is the seed, which is true here: nothing is carried between runs — no learnt constraint, no memory of bad regions, no adapting heuristic. So the number of attempts needed is geometric in the success probability, the expected total is one attempt’s cost over that probability, and the curve follows from the measured runs with nothing assumed.

The conditions transfer too, and they are what make the method a method rather than a slogan. A restart strategy helps when the distribution has a heavy tail and hurts when it does not, and the four other tessellation patches here are the case where it hurts: their runs finish between twenty-five and fifty-three steps every time, and any cutoff either fires on nothing or fires on everything.

What does not transfer #

The explanation does not, or at least not automatically, and this is where a borrowed result needs care.

In satisfiability the heavy tail is usually attributed to the structure of the instances: a randomised search can wander into a subproblem that is unsatisfiable for reasons that take exponential effort to discover, and how often that happens depends on where the instance sits relative to a phase transition in constrainedness.

Whether that account applies here is not established. This collection’s problem is a constraint satisfaction over a fixed graph with a global acyclicity condition, every backtrack is the acyclicity condition and none is a vertex, and there is no measured phase transition in the family. The tail is real and its cause is not diagnosed.

So the honest position is: the phenomenon is the known one, the remedy is the known one, and the reason the rhombille patch has a tail while its four siblings do not is a question this collection has open and the borrowed literature does not answer.

How the borrowing was actually made #

It is worth describing the sequence, because it is the ordinary way a result crosses a boundary and it looks nothing like reading a paper and applying it.

The measurement came first and was not looking for anything. A search had been built to settle whether one tessellation patch has a consistent labelling at all; it did, and the obvious next question was how much it cost. Running it from twenty different seeds produced twenty wildly different answers, which was surprising enough to run a hundred and twenty more.

At that point the table has a shape, and the shape is what does the work. A best case two hundred times below the ninth decile, with two runs in five not finishing, is not a distribution anybody meets often, and it is one that has a name. Recognising it is what turns a measurement into a borrowing.

What follows is arithmetic that took an afternoon and would have taken a week to arrive at independently — and would probably have been arrived at wrongly, since the natural thing to do with unfinished runs is to average them in at their budget, which produces a plausible number that means nothing.

Why this is a borrowing rather than a rediscovery #

The distinction matters for how the record reads, and this collection has essays on both sides of it.

The same degree-four vertex turns up in four traditions that had no contact with one another, and that is a rediscovery: the object is small, the constraints are tight, and anybody looking finds the same thing. The Yoshimura pattern was published as buckling analysis two decades before it was designed with, which is a rediscovery of a different shape: the same object found by physics and then by folders.

This is neither. The restart result was not arrived at independently here and then found to coincide; it was taken, deliberately, because the measurement produced a distribution whose shape is unmistakable and whose treatment is standard. The only thing this collection contributes is an instance with its parameters measured on a crease pattern.

Recording that is the point of this rung. A collection that measures a well-known phenomenon on its own material and then writes about it without attribution has manufactured a small false priority, and the manufacture is usually accidental — the measurement is genuinely new, the prose describes what was measured, and nothing in the writing marks which part was already known.

What a Las Vegas algorithm is, and why this one is #

The term is worth defining, because it names exactly the property that makes the arithmetic apply and it is easy to confuse with its neighbour.

A Las Vegas algorithm is one whose answer is always correct and whose running time is random. A Monte Carlo algorithm is the other way round: it finishes in a fixed time and is sometimes wrong.

The search here is squarely the first. Every labelling it returns is put back past the conditions at every vertex and past a folded sheet rebuilt from scratch, and both agree; a run that finishes has produced a witness that has been checked by machinery that did not find it. What varies is only how long the finding takes.

That matters because restarting a Monte Carlo algorithm buys nothing — the answer is as likely to be wrong the second time — while restarting a Las Vegas one is exactly the operation the theory is about. A collection that reported the search failed to find a labelling as no labelling exists would have turned the first kind into the second, and that confusion is the failure mode the whole instrument was built to avoid.

What the instance is worth #

Not nothing, and it is worth saying what an instance adds when the phenomenon is established.

It adds parameters. The optimal cutoff here is around a hundred nodes on a pattern with two hundred and eighty-two creases; the success probability at that cutoff is nineteen per cent; the gain over running to completion is a factor of thirty-two. Those numbers are specific to this problem and nobody could have predicted them from the general theory.

It adds a negative case in the same family. Four patches from the same construction, differing only in the tiling underneath, have no tail. That is a cleaner contrast than most instance families offer, because the members are related by a parameter rather than assembled from a benchmark set.

And it adds a problem class. The constraint here — an orientation of a fixed graph that must be acyclic, with local conditions restricting which orientations are available — is not a satisfiability instance and not a standard constraint benchmark. That it produces the same distribution is a small piece of evidence about how general the phenomenon is.

The dates, and what they say about the gap #

The chronology is worth setting out plainly because it makes a point about how slowly a method crosses fields.

The optimal restart schedule for a Las Vegas algorithm was published in 1993. The heavy-tailed distributions in combinatorial search were measured in 1997, and rapid randomised restarts followed in 1998. All three are firmly inside the study of search algorithms, and all three were established before the computational study of flat-foldability had produced much beyond its hardness result.

Nothing in the intervening decades appears to have applied them to a folding problem, and the reason is not obscure: nobody was running randomised backtracking searches on crease patterns, because the questions that get asked about crease patterns were being answered by enumeration on small instances or by theorems on large ones. A method for managing the runtime of a randomised search is of no use to a field with no randomised searches in it.

That is a common shape and it is the reason a borrowing is worth writing down rather than absorbing silently. The gap is not thirty years of ignorance; it is thirty years of the two fields having nothing to say to each other, ended by an instrument that happened to be built the right way.

The diagnosis, which arrived later and from the same place #

The cause left open above has since been found, and it is worth adding here rather than only where it was found, because it changes what this instance is an instance of.

The tail is produced by the search’s value ordering — which of the two letters is written first on a chosen crease. That decision was a coin toss, put there so that different seeds would return different letterings. Replace it with a constant and the patch settles in eighty steps on every run, with no spread, no unfinished runs and no distribution at all.

So the heavy tail is not a property of the rhombille patch. It is a property of a randomised search run on the rhombille patch, and removing the randomisation removes it.

Which is exactly what the borrowed literature says #

That does not weaken the borrowing. It confirms it, in the borrowed field’s own terms, and the confirmation is the sharpest thing this instance has to offer.

The heavy tails Gomes, Selman and Crato measured are tails of randomised backtracking search, not of instances. Their whole framing is that a deterministic search has one running time and a randomised one has a distribution, and that the distribution’s shape is a fact about the procedure meeting the instance rather than about either alone. An instance where withdrawing the randomness collapses the distribution to a point is the cleanest possible demonstration of that framing.

So the diagnosis this essay declined to borrow was available in the borrowed literature, and the measurement found it independently afterwards. That is a small embarrassment and a large piece of evidence: the account transfers further than the essay was willing to claim.

What the instance is worth, revised #

The parameters have to be re-read accordingly, and the revision is a demotion.

The optimal cutoff of a hundred nodes, the nineteen per cent success rate and the factor of thirty-two are all properties of one arbitrary value-ordering heuristic on this pattern, not properties of the pattern. A different coin — biasing toward valleys, say, or alternating — would move all three, and a constant removes them.

What survives is the negative half and the family structure, both of which were the more interesting contributions anyway. Four patches from one construction with no tail under either arrangement, and one with a tail that appears and vanishes with a single line, is a parameter family with a switch in it. That is a better object than a benchmark instance, and it is what somebody with the borrowed field’s instruments would want to be handed.

The habit this suggests #

There is a general lesson for a collection like this one, and it is uncomfortable in a useful way.

Every instrument here is built for a question about folding, and every instrument here is also an ordinary piece of computation — a constraint propagation, a graph search, a numerical solve, a sampler. When such an instrument produces an interesting computational result rather than an interesting result about paper, the natural instinct is to write it up as a finding about paper, because that is what the collection is about.

The correction is to ask, of any result about a procedure rather than about a pattern, whether the procedure’s own field already knows it. Here the answer was yes and was easy to find. It will not always be either.

The other direction of traffic #

It is worth asking whether anything goes the other way, since a borrowing recorded in only one direction reads as a subject with nothing to offer.

Two things here are unusual enough to be worth stating in the borrowed field’s own terms.

The first is that the constraint that does all the pruning is not a constraint the problem was posed with. The four conditions at a vertex are the problem’s stated constraints, and they never dead-end the search; the acyclicity of an orientation is a derived condition, cheap to test, and it is the entire source of backtracking. A search whose difficulty lives wholly in a derived constraint is not the usual arrangement.

The second is the family structure. Five instances generated by one construction over five different underlying tilings, four with no tail and one with a pronounced one, and with a parameter — the turn angle — that can be moved continuously through the family. Benchmark sets in the borrowed field are usually assembled from unrelated instances or generated at random near a phase transition; a parameter family whose members differ in one structural choice is a different kind of object, and the difference between the four and the one is not yet explained.

Neither is a result. Both are the shape of a thing that might become one, and both would need someone with the other field’s instruments to say whether they are interesting there.

Where the ladder goes next #

The obvious continuation is the Luby schedule. The measured curve here uses a fixed cutoff, chosen by looking at the distribution afterwards, which is not a strategy anybody could follow prospectively — the whole point of the universal schedule is that it needs no knowledge of the distribution at all. Running it on this patch and comparing against the best fixed cutoff would say how much the hindsight was worth, and the answer in the general theory is a logarithmic factor.

The other direction is the diagnosis this essay declines to borrow. If the tail has a cause here, the place to look is the structure of the arcs — how much the patch’s independent chains overlap, and whether a search’s bad early decisions are the ones that commit several chains at once. The machinery to decompose the arc graph exists in this collection and is pointed at a different question, and turning it this way is the first thing worth trying.