Luminary Research Archive
Luminary Research ArchiveIndependent scholarship
Luminary Portal
PublicEdition 7

Resolving Goldreich's Open Problem 4.1: Linear Lower Bounds for Cubic Graph Isomorphism Testing

Scott Schubr

Original PDF · First-page preview

Loading original first page…

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.

Read the full paper in the original PDF.

Edition files

  • paper.pdf117.8 KiB · pdf
    SHA-25652fe5ed7b880d453cd2b22977744230dee30338cec203ab051ae698774533685
  • Graph_Testing_Publication.zip167.9 KiB · package
    SHA-25635d49ba5b770adc5437da3f26918bd18459acd320f772d31f14bb9da42bc6ddb

Available editions

  1. Edition 7 · 2026-11-02 · public
  2. Edition 6 · 2026-10-27 · public
  3. Edition 5 · 2026-10-27 · public
  4. Edition 4 · 2026-10-24 · public
  5. Edition 3 · 2026-10-24 · public
  6. Edition 2 · 2026-10-24 · public
  7. Edition 1 · 2026-10-24 · public

Research details

Subjects
Mathematics · Computer Science & Software Systems · Combinatorics and Graph Theory · Algorithms and Complexity
Keywords
graph isomorphism testing, bounded-degree graphs, incidence queries, connected cubic graphs, subcubic graphs, query complexity, robust decoding
Manuscript date
2026-10-23
Reader reuse
none

Scope

Tight linear fixed-target isomorphism-testing query complexity at proximity 0.01 even for connected bridgeless cubic targets and inputs; every sufficiently large even order, with maximum-degree-three extensions to all sufficiently large orders.

Disclosures

AI-assisted tools supported research exploration, literature review, manuscript preparation and internal verification. The author retains responsibility for the work. Internal AI-assisted and computational checks are distinct from external human peer review.

Reproduction

The 11-page manuscript and complete editable source are supplied in a 15-member public package. README.md gives build instructions, dependencies and reproduction scope. Build reproduction is qualified by the compiler, support files and timestamp settings specified in the supplied instructions. The mathematical conclusions have analytic proofs; accompanying finite checks, where present, retain the limited scopes stated in the package.

References and related resources

  1. A. Dror, A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree Model, ECCC TR26-268 (2026).
  2. O. Goldreich and L. Tauber, Testing in the Bounded-Degree Graph Model with Degree Bound Two, LNCS 15700 (2025), 373–382.
  3. O. Goldreich, Testing Isomorphism in the Bounded-Degree Graph Model, LNCS 15700 (2025), 293–323; Open Problem 4.1.
  4. O. Goldreich and L. Tauber, On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model, LNCS 15700 (2025), 324–337.
  5. J.-Y. Cai, M. Fürer and N. Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), 389–410.
  6. V. Arvind, J. Köbler, S. Kuhnert and Y. Vasudev, Approximate Graph Isomorphism, MFCS 2012, LNCS 7464, 100–111.
  7. R. O’Donnell, J. Wright, C. Wu and Y. Zhou, Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs, SODA 2014, 1659–1677.
  8. Y. Chen, J. Flum and M. Liu, Some remarks on the uncolored versions of the original CFI-graphs, arXiv:2507.01459 (2025).
  9. M. Goetze, P. Jungeblut and T. Ueckerdt, Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs, Algorithmica 88 (2026), article 11.
  10. I. Adler, N. Köhler and P. Peng, On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing, SIAM J. Comput. 53(4) (2024), 825–883.
  11. K. Makarychev, R. Manokaran and M. Sviridenko, Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm, arXiv:1403.7721 (2014).