All Research

Abstract

We resolve Goldreich's Open Problem 4.1 negatively: testing isomorphism to a fixed cubic graph can require linearly many queries at the specified proximity 0.01. For every sufficiently large even N, there exists a known connected simple bridgeless 3-regular N-vertex target for which every randomized two-sided tester requires Ω(N) incidence queries, even when inputs are promised connected, bridgeless and cubic. Reading the whole incidence representation gives a matching O(N) upper bound, so the worst-case query complexity is Θ(N). Distance is measured by unordered edge changes with far threshold 0.01(3N/2); computation and target preprocessing are unrestricted. The proof develops a cubic encoding within Dror's sparse-code framework. Its central estimate is dist_H(b,im A)≤(2/3)dist_iso(G_b,G_0) for a 16n-vertex encoding under arbitrary uncolored bijections, including equal isolate padding. Adaptive target-middle colors, a joint row-defect budget and median rounding establish the estimate. Bounded equivariant surgeries produce connected cubic targets at every sufficiently large even order. The same encoding covers every sufficiently large integer order at proximity 0.01 with at most one isolate using the surgeries. This also attains the minimum possible maximum-degree threshold for linear fixed-target isomorphism-testing hardness.