theoremnovelunresolved_ref

Subexponential Boolean tensor network contraction

Theorem·thm:tensor-contraction·§D.1 Boolean tensor contraction

Statement (paper)

Fix positive constants

C,A,b

. Let

s\ge2

be an integer, and let

\mathcal L

be the total length of the graph and tensor descriptions of a bipartite tensor network with at most

Cs

edges and maximum degree at most

\lceil s^{9/10}\rceil

. Suppose that the number of vertices is bounded by a fixed polynomial in

s

, and that the entries belong to

\mathcal B_{P_0,\ell} =(\mathbb Z/2^{P_0}\mathbb Z)[V]/(V^\ell), \qquad 1\le P_0,\ell\le Cs.

Suppose, uniformly for every vertex and Boolean choice of its ports, that its entry can be computed from the description in time

(s+\mathcal L)^b2^{A s^{9/10}}

and space

(s+\mathcal L)^b

. Then the contraction can be computed deterministically in

(s+\mathcal L)^{O(1)} 2^{O(s/\sqrt{\log s})}

bit operations and

(s+\mathcal L)^{O(1)}

bits of space. Constants depend only on the fixed bounds in the hypotheses. In particular,

\ell=1

is permitted.

In plain English

A bipartite tensor network with at most

Cs

edges, maximum degree at most

\lceil s^{9/10}\rceil

, and entries in

(\mathbb Z/2^{P_0}\mathbb Z)[V]/(V^\ell)

can be contracted deterministically in

(s+\mathcal L)^{O(1)}2^{O(s/\sqrt{\log s})}

bit operations and polynomial space. This holds provided each entry is computable in time

(s+\mathcal L)^b2^{As^{9/10}}

and polynomial space, and

\ell=1

is allowed.

Why it's here

This is the main computational engine of the paper's appendix: the counting results (the sparse polynomial system lemma and the fixed-density bound for the main theorem) are reduced to it by encoding the instance as a bipartite network with low degree. Its proof is a recursion that deforms entries to stay integral (integral local coordinates lemma) and recovers the contraction from evaluations via tapered Hermite recovery. The call count is

\exp(O(s/\sqrt{\lambda}))

, leaves are direct sums, and a depth-first traversal gives polynomial space.

Classified novel:

Subexponential-time, polynomial-space contraction of sparse Boolean tensor networks with 2^{O(s/sqrt(log s))} cost goes well beyond known contraction methods, which run in time exponential in treewidth or linear in edge count. It is the paper's main computational engine, built on its new tapered Hermite recovery and integral local coordinates lemmas.

Uses

lemTapered Hermite recovery of F(0)lemIntegral local coordinates for tensor entries

Used by

thmSubexponential deterministic k-CNF model countinglemCounting zeros of sparse polynomial systemsclaimContraction cost gives total running timeclaimFixed-density counting via tensor contraction

Inside the proof

claimRecursive contraction algorithm is correctclaimTotal number of recursive callsclaimLeaf cost and total running time boundclaimDepth-first traversal gives polynomial space

Sources

PaperOpen

Section: §D.1 Boolean tensor contraction
Page: —
Label: thm:tensor-contraction
Line: quantitative-reduction.tex:26

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

warn
unresolved_ref
The proof environment only assembles the algorithm; the key recursion identity (eq:tensor-recursion-identity), mode expansion and mode-tuple count (eq:tensor-partition-count), and precision bound (eq:tensor-precision-bound) are argued in unlabeled text of D.4.4-D.4.6.