The cure was named first

A stretch of this collection’s work ran as follows. A search for a consistent lettering of a crease pattern was found to cost wildly different amounts from different starting seeds. The distribution was measured, recognised as heavy-tailed, and answered with a cutoff-and-restart strategy whose expected cost was computed and compared against patience.

Every step of that was somebody else’s, arrived complete, and the previous entry in this ladder recorded the first part of the borrowing. What has since become clear is that the borrowing went further than was recorded, and that the part which was not recorded is the part that mattered.

What was borrowed #

Three things, and they came as a package.

The phenomenon. That a backtracking search’s runtime can be heavy-tailed — with a maximum many times its median and a substantial share of runs not finishing at all — was established in the study of constraint satisfaction and satisfiability in the middle nineteen-nineties. It was not a curiosity but a central observation: the same solver on the same instance with different seeds spanning orders of magnitude — which is exactly what was measured here on one tessellation patch.

The response. Cutting a run off after a fixed number of steps, reseeding and starting again. The arithmetic for choosing the cutoff — the expected total is what one attempt costs divided by the chance it is the last one needed — is elementary and was worked out in that literature, along with the observation that on a sufficiently heavy tail the best cutoff is the smallest one available.

The reason it works. A heavy tail means a substantial share of runs are quick, so repeatedly buying a quick run is better than waiting out a slow one. That is the whole argument, and it is not about crease patterns.

None of the three was rediscovered here. All three were applied.

What was not borrowed, and should have been #

The literature that established restarts also established why the tail is there, and that half did not come across.

Randomisation was introduced into those solvers deliberately. A deterministic backtracking search is at the mercy of its own fixed order — on some instances it takes a bad early decision and never gets a chance to take a different one — so randomising the choices gives a distribution instead of a single outcome, and a distribution can be exploited by restarts. The tail is not an unfortunate property of hard instances discovered by accident; it is what randomisation does, and restarts are the technique for profiting from it.

So the package is coherent: randomise, get a distribution, restart to harvest its cheap end. Taking the phenomenon and the cure without the reason produces exactly the reading this collection had — that the tail belongs to the pattern and the restart is a response to the pattern’s difficulty.

There is a general shape here worth naming, because it is not specific to restarts. A technique arrives with three parts: a phenomenon, a response, and a reason the response works. The first two travel easily — they are the parts with names, the parts that appear in a summary, the parts somebody can hand over in a sentence. The third is the part that says when the technique applies, and it is the part that gets left behind.

That asymmetry is not carelessness on anybody’s part. A phenomenon and a response are what a technique is from outside; the reason is what it is from inside, and reading it requires going back to the source rather than to a summary. Every borrowing is therefore biased toward importing the parts that do not constrain application.

What a crease pattern contributed #

An instance, and one observation about it that is worth having.

The instance is a tessellation patch whose search cost runs from eighty-six steps to fifteen thousand across forty seeds, with a quarter of runs unfinished — a clean example of the phenomenon on an object from outside the literature that produced it.

The observation is that on this instance the randomisation was not introduced for the reason the literature introduces it. It was introduced so that twenty seeds would return twenty different letterings rather than one lettering twenty times, which is a purpose about variety rather than about escaping a fixed order’s bad luck. And because it was introduced for a different reason, nobody had asked whether removing it would help — and removing it costs eighty steps deterministically, against five hundred and twelve for the best restart strategy.

That is a contribution, and it is a small one and a specific one. It is not restarts are wrong, which would be false and would be arguing with a literature this collection has borrowed from. It is: a distribution should be shown to belong to the problem before a strategy is built on it, and the check costs one run.

It is worth stating the counterfactual precisely, because it is the measure of what the borrowing cost.

Had the reason travelled with the technique, the sequence would have been: notice a heavy tail; recall that a heavy tail is what randomisation produces; ask what the search is randomising and why; find that it randomises the letter choice for a reason about variety; run it once with the randomisation removed; find eighty steps; and only then, if the tail had survived, reach for a restart strategy.

That is six steps, five of which are free, and it ends with either a much cheaper search or a strategy applied on firm ground. What happened instead skipped to the strategy, which is correct arithmetic on a distribution nobody had asked about.

The gap between those two sequences is exactly the third part of the package, and its absence is not visible from anywhere inside the work. That is what makes the recording of a borrowing a practical act rather than a courtesy.

The precondition the strategy needs, and the one-line test for it #

The missing third part can be turned into something narrower than a lesson about reading sources: a test, computable from numbers this collection already had before it built the restart curve.

Restarts profit from randomisation when the fixed order is worse than the randomised distribution’s cheap end. That is the whole argument, and it is a comparison of two numbers: the deterministic cost, and the minimum over seeds.

Here they are eighty and eighty-six. The deterministic order is not merely inside the cheap end of the distribution — it is below every one of the forty seeds. So randomisation bought nothing at all at the fast end and added a tail at the slow one, which is the one arrangement under which a restart strategy cannot pay however well its cutoff is chosen.

The arithmetic of how much it did not pay is stark. The best restart strategy’s expected cost is five hundred and twelve steps against the deterministic eighty: a factor of 6.4, for correct arithmetic applied to a distribution that should not have existed.

And the test costs less than the thing it would have replaced. One deterministic run is eighty steps — about a sixth of what a single restart-managed solve is expected to cost, and roughly half of one median randomised run. The diagnostic was cheaper than the cure and cheaper than the disease.

So the rule that falls out is arithmetic rather than judgement. Before building a strategy on a distribution, run the thing once with its randomisation switched off and compare against the minimum seed. Equal or better means the distribution is the instrument’s, not the problem’s, and no cutoff will make it worth managing.

Why the record has to say so #

This collection’s habit is to record where a thing came from, and there are two reasons that matter more here than usual.

The first is ordinary honesty about credit. The same vertex found four times is the standing example of what happens when a subject does not keep its record: a result gets renamed, its history gets lost, and somebody re-derives it a fifth time.

The second is specific to a borrowed technique and it is the more useful one. A technique carries assumptions, and the assumptions do not travel with the name. The restart arithmetic assumes a distribution that is properly there — that the randomisation being exploited was introduced because a deterministic order was worse, which is exactly what was not true here. Recording the borrowing means recording the assumptions, and a collection that had written down why the literature randomises would have had the question in front of it from the beginning.

What a borrowing looks like when it goes well #

This collection borrows constantly and most of it causes no trouble, so it is worth putting a successful case beside the awkward one.

The straight skeleton was borrowed whole from computational geometry for the fold-and-cut construction, and it arrived with its reason attached: the skeleton’s arcs are equidistant from the outline’s edges, which is exactly the property a fold-and-cut pattern needs, and the property was stated at the point of borrowing rather than assumed. The construction has behaved since, and when it produced something surprising — a tie at a skeleton node that Maekawa refuses — the surprise was legible because the assumptions were written down.

The difference between the two cases is not the quality of the source. It is that in one the borrowed thing was a construction, whose correctness conditions have to be stated to use it at all, and in the other it was a strategy, which can be applied without stating anything. A construction resists being borrowed carelessly; a strategy does not.

That suggests a rule of thumb narrower than a general instruction to record sources, and more useful: the more a borrowed technique can be applied without understanding it, the more its assumptions need writing down. The techniques that are dangerous to import are the ones that are easy to import.

What is genuinely this subject’s #

It is worth being clear about the other side, because a body of work is not undone by having borrowed its instrument.

The arc test is this subject’s: a lettering’s implied statements about which panel lies above which, read off the crease list in one pass, with a cycle among them a proof that no stacking exists. That is a fact about folded paper.

The arrangement is this subject’s: testing the arcs while choosing the letters rather than after choosing them all, which is possible because a flat folded state places its panels by reflection and a reflection does not read a letter. Nothing about that is general.

The symmetry is this subject’s: swapping every letter on the sheet at once leaves every condition unchanged, which is why two constant orders cost the same node for node on a hundred and forty-two patterns.

And the negative results are this subject’s: nine patterns with no consistent lettering at all, in a region of a construction’s parameters, whose boundary is a fact about which sector at a vertex is smallest.

None of those came from anywhere else. What came from elsewhere is one instrument’s failure mode and the standard response to it.

Where the line between them actually falls #

Sorting a body of work into borrowed and original is easier to describe than to do, and the criterion this collection uses is worth stating because it is not the obvious one.

The obvious criterion is novelty: is this idea already in the literature? That is unanswerable in practice — the literature is large, the search is hard, and a negative result about it is worthless.

The criterion actually used is what the object is. A statement about crease patterns, folded states, sectors or letters is this subject’s, whoever else may also have made it. A statement about searches, distributions or strategies is not, whatever object it happened to be measured on. The arc test is about panels; the restart curve is about runtimes; and it does not matter that both were computed here on the same afternoon.

That criterion is crude and it is decidable, which is most of its value. It also produces the right answer in the awkward cases: the finding that a value order removes a tail is a statement about searches and belongs to the literature’s side, while the finding that swapping every letter is a symmetry of every flat-folding condition is a statement about paper and belongs here — even though the two were found together and the second is what makes the first safe to act on.

Which theorem was checked, and how #

Nothing in an attribution is checked by a solver, and this collection does not pretend otherwise. What is checked is everything the attribution is about: the tail is measured, the restart curve is computed from measured runs, the deterministic cost is measured on the same patch on the same day, and each of those is asserted rather than described.

The claim that the two constant orders cost the same, that a witness survives having every letter swapped, and that the coin’s spread is real and the constant’s is not — all of those are requirements that fail if the underlying numbers ever change.

The history is a different kind of claim and carries a different kind of evidence: a date, a field, and a description of what was established. It is graded the way this collection grades any other documentary claim, and it is stated as a borrowing rather than as a finding.

What the picture cannot show #

An attribution. No figure here draws the borrowing, because the borrowing is a fact about where an idea came from and figures draw measurements.

Nor does this essay settle the general question it touches. Whether randomised restarts are the right technique for search problems in general is not something a collection about folding is in a position to say, and nothing above should be read as saying it. What is said is narrower: on this problem, on these patterns, the randomisation that made the tail was introduced for a purpose unrelated to search cost, and taking it out was cheaper than managing it.

And the dates given are for the establishment of the technique rather than for its first use. Ideas of this kind rarely have a first use that anybody can identify, and the record is partitioned by subject rather than by evidence — which is a limitation of what a documentary record can support, not of anyone’s diligence.

What it costs to keep saying this #

Recording a borrowing has a price and it is worth naming, because the price is why collections stop doing it.

It makes a finding smaller. “A crease pattern’s search has a heavy tail and here is the strategy for it” is a stronger-sounding sentence than “the search literature established this in the nineties and here is an instance”, and the second is what an honest record produces. A collection that records its borrowings will always look like it has found less than one that does not.

It also puts the collection in the position of citing work it cannot fully evaluate. The nineteen-nineties results on randomised restarts were established on satisfiability instances that have nothing to do with paper, by measurements this collection has no way to reproduce, and taking them on trust is exactly what taking them on trust looks like.

Both costs are real and both are worth paying, for a reason that is specific rather than moral. A borrowed technique whose source is recorded can be checked against its source when it misbehaves. This one misbehaved, the source turned out to contain the explanation, and the explanation was reachable only because the borrowing had been written down earlier. That is the return on the discipline, and it arrived quickly.

Where the ladder goes next #

The pattern that has recurred through this work is an instrument contributing the thing it measures, and it has now happened in three places: a heavy tail from a coin, a difficulty from a branching rule, and a blemish from where the paper was cut. Each was found by asking what the instrument would report with the object removed, and that question is cheap enough that the honest conclusion is to ask it routinely rather than when something looks wrong.