Origami & Folding
what one sheet can do
Concept

Restart — where it appears

Abandoning a search after a fixed number of steps and beginning again with a fresh order of decisions. It is the right response to a cost that varies wildly between runs, because a run that has taken a long time is evidence of a bad first guess rather than of progress.

Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.

the bar is what the whole job costs if every attempt is stopped thereon the rhombille patch, read off 120 measured runsstop at 10051219% of runs finish by thenstop at 20053033% of runs finish by thenstop at 500105435% of runs finish by thenstop at 1000162442% of runs finish by thenstop at 2000263847% of runs finish by thenstop at 5000569749% of runs finish by thenstop at 100001060450% of runs finish by thenstop at 200001629160% of runs finish by thena run that never finished counts as above every cutoff, so the tail is read conservatively

Stopping is cheaper than finishing

A search whose cost varies by a factor of two hundred with nothing but the order of its guesses should not be waited out. Give up after a hundred steps, reseed and start again, and the whole job costs five hundred and twelve steps in expectation; run each attempt to twenty thousand and it costs sixteen thousand two hundred and ninety-one. Patience is thirty-two times more expensive than impatience.

complexity · Hardness of folding the bar is what the whole job costs if every attempt is stopped thereon the rhombille patch, read off 120 measured runsstop at 10051219% of runs finish by thenstop at 20053033% of runs finish by thenstop at 500105435% of runs finish by thenstop at 1000162442% of runs finish by thenstop at 2000263847% of runs finish by thenstop at 5000569749% of runs finish by thenstop at 100001060450% of runs finish by thenstop at 200001629160% of runs finish by thena run that never finished counts as above every cutoff, so the tail is read conservatively

The tail was named somewhere else

The search for a mountain-valley labelling of a tessellation patch costs eighty-four steps at best and does not finish at all two runs in five, and the cure is to stop and start again rather than to wait. None of that was discovered here. The distribution was described in the study of satisfiability solvers in the nineteen-nineties, the restart arithmetic is older still, and what a crease pattern contributes is one more instance.

history · Rediscovery the bar is what the whole job costs in expectation, in nodeson the rhombille patch, over the same 120 measured runs as the fixed cutoffsbest fixed, 100512chosen after seeing the runsunit 132226.30 times the best fixedunit 228545.58 times the best fixedunit 525424.97 times the best fixedunit 1021524.20 times the best fixedunit 2017623.44 times the best fixedunit 508481.66 times the best fixedunit 1005511.08 times the best fixedunit 2006381.25 times the best fixeda unit of one assumes nothing about the runs; every larger unit is a guess at their scale

What the hindsight was worth

The best restart cutoff for the one tessellation search with a heavy tail was read off a hundred and twenty measured runs, which nobody running the search could have done in advance. The universal schedule needs no such knowledge, and on the same runs it costs 3,222 nodes in expectation against 512 for the cutoff chosen by looking — a factor of 6.3, which is close to the base-two logarithm of that cutoff, as the theory of the schedule says it should be. A larger unit brings the schedule within a few per cent of the hindsight, and choosing the unit is choosing the scale the schedule was meant not to need.

history · Rediscovery the expected cost of the whole job under rules that learn from their own failures, in nodeson the rhombille patch, over the same 120 measured runs; the dark bar borrows its unit from other patchesbest fixed, 100512chosen after seeing the runsdouble after every failure1820at least 3.56 times the best fixeddouble after every failure, from sixteen1805at least 3.53 times the best fixedgrow by half after each failure1204at least 2.35 times the best fixeduniversal, unit of one32226.30 times the best fixeduniversal, unit from other patches8721.70 times the best fixeda rule that reads only its own failures cannot beat the best fixed cutoff, and cannot know which that is

A failure teaches a schedule nothing

The universal restart schedule costs 6.3 times the cutoff chosen by hindsight on the one folding search with a heavy tail, and the obvious repair is a schedule that learns its scale from the attempts it has already made. It cannot. A failed attempt costs exactly its cutoff and reports only that the run needed more, so every rule that chooses the next cutoff from its own failures writes down the same list whatever happens — a fixed schedule in disguise. On the measured runs, doubling after every failure costs at least 3.6 times the hindsight, and growing by half at least 2.4. What does come near is information from outside the run: the universal schedule given the longest search on four other patches as its unit costs 1.7 times the hindsight. The field that supplied the schedule reached the same conclusion, and answered it by watching runs from the inside.

history · Rediscovery each run, read at node 50, against how long it turned out to bethe top band is runs still unfinished at 20,000 nodes1234048121620times the loop test has refused the run so farnodes the run takes to finish, log₁₀finishes inside the cutofffinishes laternever finishesupright line: the refusalcount that restarts a runlevel line: the cutoff

A long run shows itself early

A restart schedule that learns only from failures was shown to be a fixed list in disguise, unable to beat the cutoff hindsight would choose. A run reports more than whether it has finished, though, and the search for a lettering of the rhombille patch already counts the one thing worth reading: how often its loop test has refused it. Read at node fifty, the count separates the runs. Of fifty runs refused eight times or more, one finishes within a hundred nodes; of seventy refused fewer times, twenty-two do. Restarting on that count costs 387 nodes in expectation against 483 for the best fixed cutoff — and chosen on half the runs and priced on the other half, 437 and 435 against 541 and 579, which on one half is cheaper than that half's own hindsight. The search literature's answer was right, and on a crease pattern it needs one number.

history · Rediscovery what happens to the tail when a refusal is readthe most recent decision is changedthe most recent decision a refusal names is changed2340306090120the runs, each search's own sorted from quickest to longestnodes, log₁₀first search: 48 of 120 unfinished at 20,000 · second: longest run 462 nodes

A trapped run is holding four letters

Thirty of the hundred and twenty searches for a lettering of the rhombille patch are refused sixteen times in their first fifty nodes, and the proposal was to find the crease that traps them. No crease can: turning every letter over turns a folded state upside down, so no single letter is ever wrong. What the thirty share is a relation among four creases, mountain, valley, mountain, valley, and the proof that it has no lettering takes seven nodes. The runs cannot find that proof, because they change their most recent decision whether or not it had anything to do with the refusal. Change instead the most recent decision the refusal names, an idea from the 1970s, and the tail is gone: all 120 finish, the longest in 462 nodes, at an average of 148 against 387 for the best restart policy, and no restart helps at all.

history · Rediscovery

Named alongside it

The objects these essays reach for when they reach for this one.

Search costRediscoveryWorst-case analysisHeuristicRandomised algorithmDecision procedureSearchAttributionBacktrackingCertificateConstraint propagationIndependent discovery

All concepts