A Quasilinear Reduction Makes END OF LINE Robust to Adversarial Gate Failures

END OF LINE asks for another endpoint in an implicitly described directed graph. Each vertex has at most one predecessor and one successor, and the input gives two small Boolean circuits for computing them. Starting from a known source, following the path must eventually reach an endpoint—but the graph may contain exponentially many vertices, so it is not supplied as an explicit picture.

The manuscript’s central claim is a reduction from this search problem to a system of numerical constraints that remains useful even when some constraints fail. For fixed positive rational constants ε and δ, a deterministic polynomial-time construction converts an END OF LINE instance of length N into a generalized circuit of total length at most A N[log₂(N + 2)]ᵇ, for fixed constants A and b. The bound counts wire addresses, auxiliary gates, and rational parameters, not only the visible gates. ^†

The reduction promises more than a small output. From every acceptable rational assignment, a deterministic polynomial-time decoder recovers an END OF LINE endpoint. An assignment is acceptable if its encoding has a fixed polynomial-length bound, every nonfailed gate meets its conditions, and at most ⌊δ|T|⌋ gates fail, where |T| is the number of gates. Failure locations may be arbitrary. The construction also guarantees that acceptable assignments exist, though finding one efficiently is a separate matter.

A generalized circuit assigns a value in [0, 1] to each wire, and each gate imposes a local condition. For example, an addition gate asks its output to equal the sum of its inputs, capped at one. The tolerance ε permits a satisfied gate to be numerically approximate. The tolerance δ permits a fraction of gates to fail altogether; a failed gate can be arbitrarily wrong. Every gate has equal weight, and a shared wire still has one consistent value.

The gate system also includes comparisons, with strict threshold rules, and Boolean gates, with weak threshold rules. Depending on whether a comparison’s antecedent is active, its output may be constrained or left free to take any value in [0, 1]. These are simultaneous constraints, not an ordinary program that runs forward: feedback and cycles are allowed, with at most one defining gate per output.

The theorem fixes ε and δ once, independently of input size. Numerical error is not required to shrink as the instance grows, and the adversary can choose which gates to break. The decoding guarantee is therefore a worst-case statement, not one that relies on errors being randomly distributed or canceling out.

The construction uses an outer representation and small inner gadgets. At the outer level, it records a computation through small tape edits and redundantly encodes consistency checks. On exact encoded data, a false certificate identity disagrees at a constant fraction of tested positions rather than being hidden in one unchecked equation.

Updating certificates without allowing the size to grow too quickly is delicate. For a product, a fixed edit gives ((a+h_a)(b+h_b)-ab = h_ab + ah_b + h_ah_b). The edit terms are fixed, so the change has degree at most one in the old variables, rather than degree two. The manuscript extends this finite-difference idea to its certificate system and reuses scratch space along a longer path.

The inner gadgets operate on outer symbols with only polylogarithmically many bits. Robust polynomial-size gadgets for those small symbols therefore contribute polylogarithmic factors; combined with an outer length of N polylog N, the total remains quasilinear. The encoding and correction radius are fixed before the input arity is chosen, rather than scaled up with the number of inputs.

These two levels control the size and reliability of the constraint system, but they do not by themselves turn a decoded computation into an endpoint-search guarantee. The construction next represents edges geometrically, then uses replicated coordinates and error accounting to make that geometric argument survive failed gates.

The reduction next translates encoded edges into geometry. Each valid vertex is represented by a separated binary word. A directed edge is implemented in four blocks: copy the next word, raise a control block, update the first word, then reset the control. The fourth block remains zero on ordinary edges. Rounded corners and an extra segment at the known source complete the path, while the source and the far end of that extra segment are explicitly excluded as answers.

A bounded-displacement field guides points along and toward these paths. Away from the desired endpoints, even a small step, clipped to the surrounding box, must move by a definite amount. Consequently, a sufficiently accurate approximate fixed point—one that barely moves—must lie near an endpoint. The local field implementation and separation estimates require substantial proof.

Because gates can fail, the circuit cannot trust a single computed geometric coordinate. It keeps many replicas of each coordinate and couples them through sparse expander averaging. Bounded updates first force replicas close to their mean without assuming that any decision is correct. The proof then accounts for ambiguous comparisons, corrupted reads, and failed computations.

The design bounds the load on each physical read and gives shared decision gadgets many output copies, so one vulnerable extraction wire cannot bear the whole guarantee. A small residual across replicas implies a small residual for their mean, making that mean an approximate fixed point. This is the bridge from the gate system’s worst-case failure allowance to the geometric endpoint argument: the replicas make a collective approximate fixed point usable without relying on any one computation being trustworthy.

Clipping complicates the averaging argument: clipping values before averaging need not equal averaging first and clipping afterward. For example, clipping 0 and 3 to the interval gives an average of 1, whereas averaging first gives 1.5. The manuscript keeps clipping inside its contraction estimate rather than swapping the operations. Its error accounting is worst-case.

The proof establishes one decoding step in detail. Let E be the endpoint’s binary word and X the corresponding block of the approximate fixed point. If rounding a coordinate at one half gives the wrong bit, that coordinate was at least one half away from its correct binary value; the squared error is therefore at least one quarter. If K of M bits are wrong and the average squared error is R², then K/4 ≤ MR², so the fraction of wrong bits is at most 4R². The bound covers every error pattern, including ties rounded to one.

The geometric and soundness bounds give R ≤ 10τ, where τ is the fixed geometric scale. Choosing τ so that 4(10τ)² is below the decoding radius puts the rounded word within the outer decoder’s correction range. Binary decoding recovers the outer representation, which recovers the vertex label and then an END OF LINE endpoint.

The paper establishes that an acceptable assignment exists by defining a continuous map from the gate rules, applying Brouwer’s fixed point theorem, and rounding a fixed point to a sufficiently fine rational mesh. Explicit margins preserve the gate conditions and give the assignment a polynomial encoding bound. This proves existence, not an efficient algorithm for finding the assignment.

The reduction’s guarantee is that any acceptable assignment, even with a fixed fraction of adversarially failed gates, yields the original search solution. Its claimed combination is fixed numerical tolerance, fixed failure tolerance, and quasilinear total size. The proof presents the local rounding argument and outlines the algebraic, geometric, and error-accounting machinery; the complete construction remains in the manuscript.