Skip to content

Conj. 3 Zotero Actions Report

Local Bibliography Snapshot

  • Treat 10_conjectures.bib as the current local mirror of the Zotero 10_conjectures collection. This report was refreshed against that file.

Papers To Manually Add

  • None at the current Conjecture 3 frontier.
  • The previously flagged low-order matroid-structure papers are not current blockers for the active compiler-native CD route and are therefore not pending manual addition in this report state.

Already In 10_conjectures.bib / Library

  • Title: Locally Testable Codes and Expanders Bib key: dinurLocallyTestableCodes Relevance: Primary source for [[ltc-sparse-cut-product-decomposition.md]] and [[strong-ltc-constraint-graph-small-set-expander.md]]. It is the first source on the graph that turns strong LTC irreducibility into a theorem about sparse cuts and small-set expansion of tester graphs.

  • Title: Locally Testable Codes and Cayley Graphs Bib key: gopalanLocallyTestableCodes2014 Relevance: Primary source for the new nodes [[smooth-ltc-cayley-characterization.md]] and [[cayley-ltc-characterization-insufficient-for-balanced-cut-rank.md]]. It shows that smooth LTC is exactly a Cayley-graph spectral and metric phenomenon, which is why any hypothesis merely equivalent to LTC is now ruled out as sufficient for the balanced-cut frontier.

  • Title: Locally Testable Codes with Constant Rate, Distance, and Locality Bib key: dinurLocallyTestableCodes2022 Relevance: Primary source for [[left-right-cayley-ltc-from-local-agreement-plus-expansion.md]] and a stronger foundation for [[quantum-tanner-constituent-ltc.md]]. It isolates the local-to-global package of local tensor agreement testability plus two-direction expansion that now looks like the cleanest candidate extra ingredient beyond plain LTC.

  • Title: Locally Testable Codes via High-Dimensional Expanders Bib key: diksteinLocallyTestableCodes2020 Relevance: Primary source for [[agreement-expander-lifts-local-testability.md]]. It shows that the left-right-Cayley style local-to-global phenomenon sits inside a broader agreement-expander framework, which clarifies that the remaining missing step is not another tester-side lifting theorem but an intrinsic interface-complexity theorem.

  • Title: A Decomposition Theory for Binary Linear Codes Bib key: local entry with arXiv identifier cs/0611028 Relevance: Primary source for [[exact-2-separation-is-2-sum.md]], [[nonminimal-exact-3-separation-is-3-sum.md]], and the low-order decomposition side of the intrinsic cut-rank frontier.

  • Title: Tangles, tree-decompositions and grids in matroids Identifier: DOI 10.1016/j.jctb.2007.10.008 Relevance: Primary source for [[tangle-order-equals-branchwidth.md]] and part of [[good-codes-have-weakly-4-connected-log-branchwidth-minor.md]]. It turns branchwidth into an explicit tangle-order statement, which is the current bridge from code width to intrinsic matroid connectivity.

  • Title: What is a 4-Connected Matroid? Identifier: DOI 10.37236/12467 Relevance: Primary source for [[large-tangle-yields-weakly-4-connected-minor.md]], [[tangle-breadth-gives-k-connected-set.md]], [[large-k-connected-set-persists-in-weakly-4-connected-minor.md]], and [[large-k-connected-set-gives-balanced-cut-rank.md]]. It is now the key intrinsic-side source because it turns large tangles and large breadth into concrete highly connected sets and weakly 4-connected minors.

  • Title: Tangles, trees, and flowers Identifier: DOI 10.1016/j.jctb.2013.03.002 Relevance: Primary source for [[robust-tangle-tree-displays-all-nonsequential-separations.md]]. It is the first source on the graph that says a robust high-order tangle does not admit arbitrary nontrivial low-order cuts: up to tangle-equivalence they are organized by one tree, so the live gap becomes robustness, nonsequentiality, and flower exclusion.

  • Title: The structure of crossing separations in matroids Identifier: DOI 10.1016/j.aam.2007.05.004 Relevance: Primary source for [[every-k-flower-is-anemone-or-daisy.md]] and [[k-flower-local-connectivity-classification.md]]. It turns the fixed-order crossing-separation regime into a small set of flower templates governed by only a few local-connectivity parameters.

  • Title: The structure of the 3-separations of 3-connected matroids Identifier: DOI 10.1016/j.jctb.2004.03.006 Relevance: Primary source for [[maximal-partial-3-tree-displays-all-nonsequential-3-separations.md]]. It is the cleanest low-order prototype on the graph: cut-rank 2 is already globally organized by a partial 3-tree with anemone and daisy vertices.

  • Title: The structure of the 3-separations of 3-connected matroids II Identifier: DOI 10.1016/j.ejc.2006.01.007 Relevance: Primary source for [[reduced-partial-3-tree-is-unique.md]]. It upgrades the partial-3-tree template from mere existence to a canonical reduced form.

  • Title: Exposing 3-separations in 3-connected matroids Identifier: DOI 10.1016/j.aam.2010.10.009 Relevance: Primary source for [[well-positioned-nonsequential-3-separation-has-safe-element.md]]. It shows that a well-positioned fully closed nonsequential 3-separator contains a safe element whose removal preserves 3-connectivity and does not expose new 3-separations.

  • Title: The structure of equivalent 3-separations in a 3-connected matroid Identifier: DOI 10.1016/j.aam.2005.01.003 Relevance: Primary source for [[nonsequential-equivalence-class-without-special-gadgets-is-canonical-chain.md]]. It shows that, after excluding a small menu of special gadgets, a nonsequential equivalence class becomes a canonical chain of maximal segments and cosegments with only local reorder freedom.

  • Title: The structure of 3-connected matroids of path width three Identifier: DOI 10.1016/j.ejc.2005.10.005 Relevance: Primary source for [[sequential-matroid-has-canonical-left-right-ends.md]] and [[normalized-sequential-orderings-have-bounded-end-variation.md]]. It turns the remaining sequential low-order loophole into canonical end-templates with tightly bounded local variability.

  • Title: Profiles of Separations: in Graphs, Matroids, and Beyond Identifier: DOI 10.1007/s00493-017-3595-y Relevance: Primary source for [[canonical-tree-distinguishes-all-matroid-tangles.md]]. It supplies the canonical, automorphism-invariant tangle-decomposition theorem now recorded on the graph, which is the cleanest symmetry-respecting decomposition tool available for structured families such as Quantum Tanner parity-check matroids.

  • Title: A unified treatment of linked and lean tree-decompositions Bib key: erdeUnifiedTreatmentLinked2018 Relevance: Primary source for [[lean-matroid-bag-gives-rank-connected-set.md]]. It adds the first theorem on the graph that turns optimal matroid tree-decompositions into explicit bag-local connectivity objects, sharpening the intrinsic frontier from “find width” to “concentrate width into a usable bag.”

  • Title: Matroid 3-connectivity and branch width Bib key: geelenMatroid3connectivityBranch2015 Relevance: Primary source for [[high-tangle-order-gives-large-tangle-independent-set.md]]. It shows that large tangle order already forces large independent and coindependent removable sets, which clarifies that the remaining missing step is concentration, not the existence of structured large subsets.

  • Title: Branch-width and well-quasi-ordering in matroids and graphs Bib key: geelenBranchwidthWellquasiorderingMatroids2002 Relevance: Primary source for [[linked-branch-decomposition-exists-at-optimal-width.md]]. It shows that branchwidth can always be witnessed by an optimal linked branch decomposition, which is the cleanest coordinate-tree normalization currently available on the intrinsic side.

  • Title: Matroid tree-width Bib key: hlinenyMatroidTreewidth2006 Relevance: Primary source for [[branchwidth-and-matroid-treewidth-are-equivalent.md]] and [[good-codes-have-logarithmic-matroid-treewidth.md]]. It is the exact comparison theorem that turns the existing good-code branchwidth lower bound into a matroid tree-width lower bound and hence into the lean-decomposition route.

  • Title: Rank-width and vertex-minors Bib key: oumRankwidthVertexminors2005 Zotero key: 2I6LL2QJ Relevance: Primary source for [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]] and [[basis-robust-fundamental-graph-loads-must-be-pivot-invariant.md]]. It gives the exact identity \lambda_M(X)=\mathrm{cutrk}_G(X)+1 for fundamental graphs and shows that different fundamental graphs of the same binary matroid are related by pivoting, which is now the key basis-robustness obstruction on the compiler-native CD route.

  • Title: On a general framework for network representability in discrete optimization Bib key: iwamasaGeneralFrameworkNetwork2018 Zotero key: 3VTJSQDT Relevance: Primary source for [[boolean-network-generalization-adds-no-nonmonotone-power-for-stabilizer-cut-rank.md]]. It proves that generalized Boolean (k,\rho,\sigma) network representability adds only monotone functions beyond the classical hidden-vertex graph-cut class, so for nontrivial symmetric stabilizer cut-rank functions the broader framework collapses back to the ordinary hidden-vertex question.

  • Title: Matroid Pathwidth and Code Trellis Complexity Bib key: local entry with arXiv identifier 0705.1384 Relevance: Primary source for [[matroid-pathwidth-equals-code-trellis-width.md]]. It makes the ordering-based side exact by identifying code trellis-width with matroid pathwidth, so the existing sweep-hardware lower bound route is now properly phrased in intrinsic matroid language.

  • Title: Quantum Tanner codes Zotero key: 625UUKHI Relevance: Core expander-style QLDPC anchor family used throughout the current lower-bound path.

  • Title: Explicit Instances of Quantum Tanner Codes Bib key or local identifier: not yet recorded in this report before your latest sync Relevance: Frontier paper on concrete finite Quantum Tanner instances and overhead analysis. Useful for the explicitness side, but it does not by itself close the asymptotic Theorem-17 component-code gap.

  • Title: Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs Bib key or local identifier: not yet recorded in this report before your latest sync Relevance: Core source for the vc-treewidth obstruction and the code-on-graphs route now on the graph.

  • Title: On Minimal Tree Realizations of Linear Codes Bib key or local identifier: not yet recorded in this report before your latest sync Relevance: Core source for the exact tree-edge state-dimension formula and for the branchwidth versus treewidth comparison used by the new trellis-width route.

  • Title: Eigenvalues and expanders Bib key: alonEigenvaluesExpanders1986 Relevance: Supplies the standard spectral-gap to edge-expansion bridge used in the explicit-family theorem chain.

  • Title: The bisection width and the isoperimetric number of arrays Zotero key: ICYUU8Y9 Relevance: Supplies the exact static-2D cut-capacity bottleneck.

  • Title: Packet routing and job-shop scheduling in O(congestion+dilation) steps Zotero key: BUPET47W Relevance: Supports the congestion/dilation compilation abstraction.

  • Title: Routing permutations on graphs via matchings Zotero key: RN3DM5NS Relevance: Gives the routing-number formulation for swap-based token movement and supports the tightness discussion.

  • Title: Optimal quantum circuits for nearest-neighbor architectures Zotero key: DIJE9UFB Relevance: Records the key model-sensitivity contrast between nonadaptive SWAP-only compilation and stronger adaptive architectures.

  • Title: Computing Efficiently in QLDPC Codes Zotero key: X777HH8Y Relevance: Important adjacent contrast. It shows some QLDPC families admit efficient logical Clifford compilation via automorphisms and transversal structure, but it does not supply a static-2D SWAP-only embedding theorem. Keep this in view to avoid overclaiming the lower bound.

  • Title: Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes Bib key: delfosseBoundsStabilizerMeasurement2021 Relevance: Now the main lower-bound anchor for the minimal static-2D target and the source of the cut theorem closest to CD(T_n,\mathfrak G).

  • Title: Connectivity constrains quantum codes Bib key: baspinConnectivityConstrainsQuantum2022 Relevance: Supplies the separator-profile language and the strongest code-connectivity obstruction currently on the graph.

  • Title: A lower bound on the overhead of quantum error correction in low dimensions Bib key: baspinLowerBoundOverhead2023 Relevance: Provides the more model-general 2D syndrome-depth theorem and the current best rigorous support for the conjectured threshold consequence.

  • Title: Edge-Coloring Bipartite Multigraphs in O(E log D) Time Bib key: coleEdgecoloringBipartiteMultigraphs2001 Relevance: Still the cleanest source for decomposing a Tanner interaction graph into constant many matching layers inside the cut-based route.

  • Title: Routing by matching on convex pieces of grid graphs Zotero key: L4MK3W5N Relevance: Confirms that the Omega(sqrt(n)) scale is also the right routing scale for static 2D grid pieces up to constants.

  • Title: Quantifying nonlocality: how outperforming local quantum codes is expensive Zotero key: NXQRWERY Relevance: Independent lower-bound support that genuinely good QLDPC behavior in 2D demands substantial nonlocal connectivity.

  • Title: Constant-overhead quantum error correction with thin planar connectivity Zotero key: QJMIN3T5 Relevance: Clean positive escape route showing which extra hardware resource invalidates the static-grid barrier.

  • Title: Toward a 2D local implementation of quantum low-density parity-check codes Zotero key: LCPJCHMC Relevance: Most direct recent implementation boundary paper for resource-augmented 2D qLDPC layouts.

  • Title: Hierarchical memories: Simulating quantum LDPC codes with local gates Bib key: pattisonHierarchicalMemoriesSimulating2025 Relevance: Strongest current theorem-level threshold escape route within 2D local gates, but only after changing the code family through hierarchical concatenation.

  • Title: Surface Code Compilation via Edge-Disjoint Paths Bib key: beverlandSurfaceCodeCompilation2022 Relevance: Clean teleportation-style boundary marker showing how edge-disjoint ancilla paths can beat plain SWAP routing for parallel long-range Clifford operations.

Deferred

  • Title: An Optimal Routing Algorithm for Mesh-Connected Parallel Computers Reason not added in this cycle: Historically relevant, but the 2022 convex-grid routing paper is the cleaner modern source for the Theta(sqrt(n)) static-mesh routing scale.

  • Title: Single-Shot Decoding of Good Quantum LDPC Codes Reason not added in this cycle: Relevant to repeated-round QEC and adjacent to Conjectures 2 and 3, but still not needed for the present static-2D SWAP-only round lower bound.