Pith. sign in

REVIEW 2 major objections 5 minor 65 references

Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Memory-efficient tensor contraction orders are exactly carving decompositions, and treewidth finds them within a 4/3 factor.

desk verdict A solid, well-credited paper with a genuinely new memory bound for tensor-network contraction and a useful counting tool; the one load-bearing gap is an omitted but fillable proof. read the letter →

arxiv 1908.04381 v2 pith:DEFHIVU5 submitted 2019-08-12 cs.DS cs.AIcs.LO

Jeffrey M. Dudek , Leonardo Dueñas-Osorio , Moshe Y. Vardi This is my paper · ORCID
classification cs.DScs.AIcs.LO
keywords weightedmodelcountingtensornetworkcontractiontreedecompositioncarvingmaxranklinegraphfactor-treemethod
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Constrained counting—the problem of computing the total weight of satisfying assignments of a Boolean formula—can be reduced to contracting a tensor network, but the cost of that contraction depends on the order in which tensors are multiplied. This paper establishes that the memory cost of an order is governed by an exact graph quantity: the carving width of the network's structure graph, i.e. the largest number of edges crossing a cut in a binary tree whose leaves are the network's tensors. It then shows that tree decompositions, which have mature heuristic solvers, can be converted into carving decompositions, and that a tree decomposition can also guide a factoring step that breaks high-rank tensors into rank-3 pieces. For the tensor networks that arise from counting formulas, this yields contraction trees whose max rank is at most about four-thirds the treewidth, a threefold improvement over the prior bound. The implemented counter solves weighted-counting instances that established exact counters cannot solve within the timeout, so the method is a useful addition to a counting portfolio.

What carries the argument

The identity that carries the argument is the equality between max rank and carving width (Theorem 3): every cut of the structure graph corresponds to one recursive subcontraction, and the edges crossing the cut are exactly the free indices of the intermediate tensor. The constructive devices are the line graph $\mathrm{Line}(G)$, whose tree decompositions become carving decompositions of $G$ at a cost of at most $+1$ in width; and the Factor-Tree construction, which uses a tree decomposition of the structure graph to choose a dimension tree for each tensor and replaces each tensor with a Hierarchical Tucker representation—a tree-shaped network of rank-3 tensors. The proof's simplified graph $H$, built by copying each bag of the tree decomposition and connecting the copies according to the original edges, is what lets the authors control the carving width of the factored network: they partition each bag's vertices into three groups, so that arcs inside the decomposition cross at most $w+1$ shared labels plus one extra vertex for each third of a bag.

What would settle it

Take a CNF formula in which some variable appears $k$ times, build the rank-$k$ variable tensor from the paper's reduction, and test every dimension tree for a factorization into rank-3 tensors whose bond dimension is no larger than the Boolean domain size $2$; if any dimension tree needs a larger bond dimension, the tree-factorability premise fails and Theorem 6 cannot be applied to counting instances.

Watch

Extended reading notes

Core claim

The paper's central claim is that structure-based contraction-order search reduces to well-studied graph decomposition. Theorem 3 gives an exact equivalence: a tensor network has a contraction tree of max rank $w$—the largest tensor that must be held in memory during recursive contraction—if and only if its structure graph (tensors as vertices, indices as edges, all free indices attached to a special free vertex) has a carving decomposition of width $w$, and each can be built from the other in linear time. Consequently a planar network's memory-optimal contraction order is computable in cubic time. On the constructive side, Theorem 4 shows that a tree decomposition of the line graph of width $w$ yields a carving decomposition of width at most $w+1$, so the Line-Graph method produces contraction trees that match the memory model of modern tensor libraries. Theorem 6 then shows that for networks of tree-factorable tensors with at most three free indices, a tree decomposition of the structure graph of width $w$ guides a factoring of every tensor into rank-3 tensors without increasing the bond dimension (the largest domain among shared indices), after which the factored network has a contraction tree of max rank at most $\lceil 4(w+1)/3\rceil$, compared with $3(w+2)$ from prior constructions. The authors assert that all tensors produced by their weighted-model-counting reduction are tree-factorable, which is the cornerstone that lets the counting application inherit the $4/3$ improvement.

Load-bearing premise

The paper asserts, without an accompanying proof or construction, that every tensor produced by its reduction from weighted model counting is tree-factorable, including the requirement that factoring never enlarge the bond dimension beyond the original index domains; if some variable tensor violates that requirement, the improved max-rank bound no longer applies to the counting instances the paper targets.

Editorial extensions

If this is right

  • Planar tensor networks get memory-optimal contraction orders in cubic time, because optimal carving decompositions of planar graphs are polynomial-time computable.
  • Any tree-decomposition heuristic can serve as a contraction-order engine: the resulting max rank is at most one more than the treewidth of the line graph, matching the memory model of modern tensor libraries.
  • Weighted-model-counting networks can be preprocessed so that contraction memory scales with the structure graph's treewidth times roughly $4/3$ rather than times $3$, changing which instances are feasible.
  • Tensor-network counters become portfolio components: on standard weighted-counting benchmarks, the factoring-based variants solve instances that dedicated exact counters time out on.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the paper's tree-factorability assertion extends to constraints beyond OR clauses (parity, cardinality, pseudo-Boolean), the same Factor-Tree machinery would give treewidth-governed memory for those counting problems; the paper gestures at this direction but does not prove it.
  • The factor-of-three gap between the new bound and prior constructions invites a search for graphs whose true optimal factored carving width is close to $4(w+1)/3$; a tight example would test whether the analysis can be sharpened further.
  • Because max rank is a memory measure, FT's low-rank contraction trees should make tensor counting a better fit for GPU and parallel contraction, where memory rather than arithmetic often decides feasibility.
  • The exact correspondence with carving width suggests that preprocessing methods for model counting should be evaluated by how much they reduce carving width, not just treewidth, since carving width is the quantity that directly bounds contraction memory.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper develops two structure-based methods, LG and FT, for finding contraction trees of small max rank in tensor networks, and applies them to weighted model counting through the reduction of Theorem 1. The theoretical core is: Theorem 3 identifies max-rank-optimal contraction trees with carving decompositions of the structure graph, using a free vertex to handle free indices; Theorem 4 converts a width-w tree decomposition of the line graph into a carving decomposition of width at most w+1; and Theorem 6 factors networks of tree-factorable tensors with at most three free indices into rank-at-most-3 tensors so that the resulting network has a contraction tree of max rank at most ceil(4(w+1)/3). These algorithms are implemented in TensorOrder using three heuristic tree-decomposition solvers and are evaluated on vertex-cover counting and Bayesian-inference benchmarks.

Significance. If the results hold, the paper gives a clean formal connection between tensor-network contraction optimization and carving/tree decompositions, and a substantial improvement in the max-rank upper bound for structured high-rank tensors: from the prior 3(w+2) bound to ceil(4(w+1)/3). The experimental section is careful, the code, benchmarks, and data are publicly available, and the portfolio claim is appropriately modest. The theoretical results are mostly proved in the text, and prior work, including de Oliveira Oliveira's contribution, is properly credited. However, the applicability of Theorem 6 to the paper's target instances depends on a tree-factorability assertion that is currently stated without proof, and the theorem's bond-dimension conclusion is stronger than the proof supports. Both issues are local and fixable, but they must be addressed before the central claims can be regarded as fully supported.

major comments (2)
  1. [Section 6, Definition 10 and Theorem 6] The sentence 'All tensors in the reduction of Theorem 1 from weighted model counting to tensor networks are tree factorable' is load-bearing: it is the step that lets Theorem 6's bound apply to the counting instances that the paper targets, and the variable and clause tensors from Theorem 1 have unbounded rank. No construction or proof is supplied in the text. The claim is plausible and, in my assessment, true: a variable tensor can be factored by a binary tree of equality/copy tensors with the weights applied at the root, and a clause tensor can be factored by literal-flip leaves and a binary tree of OR gates, both with bond dimension 2. But the authors should include this proof, or an explicit reference, in the revision.
  2. [Section 6, Theorem 6] The conclusion that M 'has the same bond dimension as N' is not proved and is false in general. Definition 10(4) only requires each factored network N_A to have bond dimension bounded by |[i]| for some original index i of A; if that index is a free index of N, its domain is not bounded by the bond dimension of N as defined in Section 3.2. For example, a tensor A with two bond indices of domain 2 and one free index of domain 3 can be represented by placing A (relabelled) at the internal node of a three-leaf dimension tree with copy tensors at the leaves, giving a factored network with a bond of dimension 3 even though N has bond dimension 2. The proof in Parts 1-5 never addresses bond dimension. This does not threaten the weighted-model-counting application, since all indices in the Theorem 1 reduction have domain {0,1}, but the theorem statement and proof need to be corrected.
minor comments (5)
  1. [Lemma 5] In the last sentence of the proof, 'ψ∘f = δG' should be 'ψ∘g = f', and the phrase 'Since f is an edge clique cover' should refer to the image of f rather than to f itself.
  2. [Theorem 6, Part 1] The notation δ_H(v) is used before H is defined; it should be δ_G(v). Also, 'let N_A={N_A}' should read 'N_A={A}'.
  3. [Theorem 6, Part 4] In the bound for the partition induced by c_a, the second inclusion 'πG(π_T^{-1}(o))⊆χ(p)' should be 'πG(π_T^{-1}(p))⊆χ(p)'.
  4. [Section 7.3 and Section 8] The concluding sentence 'both LG and FG are useful as part of a portfolio' should read 'LG and FT'. In addition, the sentence in Section 7.3 that the non-factoring tensor-based methods 'were only able to count a single benchmark' is ambiguous: it should say whether this is a per-method or collective statement.
  5. [Theorem 3 proof] After removing the leaf z and its incident arc, the contraction tree S' is rooted at the neighbor of z; stating this explicitly would make the construction of the contraction tree immediate.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main bounds are derived from genuine decomposition arguments; the unproved tree-factorability assertion is an omitted proof, not a circular step.

full rationale

The derivation chain is self-contained. Theorem 1 proves that the tensor-network contraction equals the weighted model count by expanding the Definition 5 sum and observing that the variable tensors zero out inconsistent assignments while the clause tensors evaluate the clauses; the target quantity W(phi) is not used to define the contraction tree or the max-rank bound. Theorem 3 is a proven equivalence: Lemma 2 identifies the free indices of a subnetwork with the cut edges of the structure graph, so carving width equals max rank; the no-free-index version is explicitly credited to de Oliveira Oliveira, so the extension is not imported through an author-uniqueness principle. Theorem 4 is derived from Lemma 5 and the path property of tree decompositions, giving carving width at most treewidth(Line(G)) + 1 without assuming its own conclusion. Theorem 6 assumes only the explicitly stated tree-factorability condition (Definition 10) and then constructs the factored network M, the auxiliary graph H, a carving decomposition S, and bounds the width of each arc type; the constant ceil(4(w+1)/3) is a width calculation, not a restatement of the input. The only soft spot is the unproved sentence in Section 6 immediately after Definition 10: "All tensors in the reduction of Theorem 1 from weighted model counting to tensor networks are tree factorable." This is a completeness gap for the application of Theorem 6 to counting instances, not a circular step, because the claim is logically independent of the theorem and explicit factorizations exist (copy/equality tensors for variable tensors and OR-with-literal-flip gates for clause tensors). The Vardi self-citations ([22], [43], [50], [55]) are background references in database join optimization and reliability and do not carry the main derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The central Theorem 6 bound is parameter-free given the treewidth w; no constant is fitted to data. The main unpaid premises are tree-factorability of the counting tensors (asserted, not proved), the max-rank memory model, and the quality of heuristic tree-decomposition solvers for the empirical portfolio claim. None of these is circular; each is a domain assumption whose failure would narrow the practical reach of the method rather than invalidate the conditional theorem.

assumptions (4)
  • domain assumption All tensors from the Theorem 1 reduction are tree-factorable per Definition 10, with bond dimension no larger than the original index domain (property 4).
    Stated in Section 6 after Definition 10 without a construction or proof. Load-bearing for FT: if a variable tensor with many appearances cannot be factored into rank-3 tensors with bond dimension 2, the max-rank bound of Theorem 6 would not apply to the counting benchmarks.
  • domain assumption Max-rank is the correct memory cost model for modern tensor libraries that contract by summing shared indices simultaneously.
    Section 3.3 defines max-rank and contrasts it with contraction complexity. The theoretical results (Theorems 3, 4, 6) are stated in terms of max-rank; the empirical speedups assume this model matches numpy's actual memory use. Plausible and supported by the rank plots, but still a modeling choice.
  • standard math Prior standard results used in the alternative proof of Theorem 4: Harvey-Wood Theorem 2.4 (line graph treewidth vs vertex congestion) and Alvarez et al. Lemma 2 (carving width vs vertex congestion), plus treewidth bounded by three times carving width.
    Explicitly cited in Section 5.2 and the appendix; taken as correct background.
  • domain assumption Heuristic tree-decomposition solvers (Tamaki, FlowCutter, htd) find sufficiently narrow decompositions on target incidence graphs within the time budget.
    The portfolio claims in Section 7 depend on solver quality. The paper mitigates this by testing three solvers and taking the best, but the guarantees are heuristic.
invented entities (1)
  • Free vertex z in the structure graph (Definition 8)
    purpose: A fresh graph vertex added to absorb all free indices of a tensor network, so carving decompositions and the max-rank equivalence (Theorem 3) extend to networks with free indices.
    Formal construction device, not a physical or empirical entity. It is justified by the proofs in Section 5; it does not add a load-bearing ontological assumption because removing it would only restrict Theorem 3 to networks without free indices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions." pith.science (2026). https://pith.science/paper/DEFHIVU5

@misc{pith2026190804381,
  author       = {Pith},
  title        = {Pith review of: Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DEFHIVU5}},
  note         = {Machine review of arXiv:1908.04381}
}
read the original abstract

Constrained counting is a fundamental problem in artificial intelligence. A promising new algebraic approach to constrained counting makes use of tensor networks, following a reduction from constrained counting to the problem of tensor-network contraction. Contracting a tensor network efficiently requires determining an efficient order to contract the tensors inside the network, which is itself a difficult problem. In this work, we apply graph decompositions to find contraction orders for tensor networks. We prove that finding an efficient contraction order for a tensor network is equivalent to the well-known problem of finding an optimal carving decomposition. Thus memory-optimal contraction orders for planar tensor networks can be found in cubic time. We show that tree decompositions can be used both to find carving decompositions and to factor tensor networks with high-rank, structured tensors. We implement these algorithms on top of state-of-the-art solvers for tree decompositions and show empirically that the resulting weighted model counter is quite effective and useful as part of a portfolio of counters.

Figures

Figures reproduced from arXiv: 1908.04381 by the authors.

Figure 1
Figure 1. The tensor network (left) produced by Theorem 1 on [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. When FT is run on the shown initial tensor network (l [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Median solving time (top) and max-rank of the compu [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: A cactus plot of the number of benchmarks solved by v [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]
Figure 5
Figure 5. Figure 5: The number of probabilistic-inference benchmark [PITH_FULL_IMAGE:figures/full_fig_p022_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 60 canonical work pages

  1. [1]

    Bacchus, S

    F. Bacchus, S. Dalmao, T. Pitassi, Algorithms and complexity resu lts for #SAT and Bayesian inference, in: Proc. of FOCS, 2003, pp. 340–35 1. 23

    work page 2003

  2. [2]

    Domshlak, J

    C. Domshlak, J. Hoffmann, Probabilistic planning via heuristic forwa rd search and weighted model counting, Journal of Artificial Intellige nce Re- search 30 (1) (2007) 565–620

    work page 2007

  3. [3]

    C. P. Gomes, A. Sabharwal, B. Selman, Model counting, in: Handb ook of Satisfiability, IOS Press, 2009, pp. 633–654

    work page 2009

  4. [4]

    L. G. Valiant, The complexity of enumeration and reliability problems , SICOMP 8 (3) (1979) 410–421

    work page 1979

  5. [5]

    Oztok, A

    U. Oztok, A. Darwiche, A top-down compiler for sentential decis ion dia- grams., in: Proc. of IJCAI, 2015, pp. 3141–3148

    work page 2015

  6. [6]

    Thurley, SharpSAT: counting models with advanced componen t caching and implicit BCP, in: Proc

    M. Thurley, SharpSAT: counting models with advanced componen t caching and implicit BCP, in: Proc. of SAT, 2006, pp. 424–429

    work page 2006

  7. [7]

    J. D. Biamonte, J. Morton, J. Turner, Tensor network contra ctions for #SAT, Journal of Statistical Physics 160 (5) (2015) 1389–1404

    work page 2015

  8. [8]

    Biamonte, V

    J. Biamonte, V. Bergholm, Tensor networks in a nutshell, arXiv pr eprint arXiv:1708.00006

    arXiv

Show all 65 references
  1. [9]

    Cichocki, Era of big data processing: A new approach via tenso r net- works and tensor decompositions, arXiv preprint arXiv:1403.2048

    A. Cichocki, Era of big data processing: A new approach via tenso r net- works and tensor decompositions, arXiv preprint arXiv:1403.2048

    arXiv

  2. [10]

    Or´ us, Tensor networks for complex quantum systems, Na ture Reviews Physics 1 (9) (2019) 538–550

    R. Or´ us, Tensor networks for complex quantum systems, Na ture Reviews Physics 1 (9) (2019) 538–550

    2019

  3. [11]

    F. R. Kschischang, B. J. Frey, H.-A. Loeliger, Factor graphs a nd the sum- product algorithm, IEEE Transactions on information theory 47 (2 ) (2001) 498–519

    2001

  4. [12]

    B. W. Bader, T. G. Kolda, Efficient matlab computations with spar se and factored tensors, SIAM Journal on Scientific Computing 30 (1) (2 007) 205– 231

  5. [13]

    S. Hirata, Tensor contraction engine: Abstraction and autom ated paral- lel implementation of configuration-interaction, coupled-cluster, and many- body perturbation theories, The Journal of Physical Chemistry A 107 (46) (2003) 9887–9897

    2003

  6. [14]

    Kjolstad, S

    F. Kjolstad, S. Kamil, S. Chou, D. Lugato, S. Amarasinghe, The tensor algebra compiler, Proc. of PACMPL (2017) 77

    2017

  7. [15]

    Vasilache, O

    N. Vasilache, O. Zinenko, T. Theodoridis, P. Goyal, Z. DeVito, W. S. Moses, S. Verdoolaege, A. Adams, A. Cohen, Tensor comprehensions: Fr amework- agnostic high-performance machine learning abstractions, arXiv p reprint arXiv:1802.04730. 24

    arXiv

  8. [16]

    J. Kim, A. Sukumaran-Rajam, V. Thumma, S. Krishnamoorthy, A. Pa- nyala, L.-N. Pouchet, A. Rountev, P. Sadayappan, A code genera tor for high-performance tensor contractions on gpus, in: Proc. of CGO , IEEE Press, 2019, pp. 85–95

    2019

  9. [17]

    Nelson, A

    T. Nelson, A. Rivera, P. Balaprakash, M. Hall, P. D. Hovland, E. J essup, B. Norris, Generating efficient tensor contractions for gpus, in: P roc. of ICPP, IEEE, 2015, pp. 969–978

    2015

  10. [18]

    Pfeifer, J

    R. Pfeifer, J. Haegeman, F. Verstraete, Faster identificatio n of optimal contraction sequences for tensor networks, Physical Review E 9 0 (3) (2014) 033315

    2014

  11. [19]

    Kourtis, C

    S. Kourtis, C. Chamon, E. R. Mucciolo, A. E. Ruckenstein, Fast counting with tensor networks, arXiv preprint arXiv:1805.00475

    arXiv

  12. [20]

    S.-J. Ran, E. Tirrito, C. Peng, X. Chen, L. Tagliacozzo, G. Su, M . Lewen- stein, Lecture notes of tensor network contractions, arXiv pre print arXiv:1708.09213

    arXiv

  13. [21]

    Greco, N

    G. Greco, N. Leone, F. Scarcello, G. Terracina, Structural d ecomposition methods: Key notions and database applications, in: A Comprehens ive Guide Through the Italian Database Research Over the Last 25 Yea rs, Springer, 2017, pp. 253–267

    2017

  14. [22]

    B. J. McMahan, G. Pan, P. Porter, M. Y. Vardi, Projection pus hing revis- ited, in: Proc. of EDBT, 2004, pp. 441–458

    2004

  15. [23]

    H. Dell, C. Komusiewicz, N. Talmon, M. Weller, The PACE 2017 param - eterized algorithms and computational experiments challenge: The second iteration, in: Proc. of IPEC, 2017, pp. 30:1–30:12

    2017

  16. [24]

    Abseher, N

    M. Abseher, N. Musliu, S. Woltran, htd- a free, open-source f ramework for (customized) tree decompositions and beyond, in: Proc. of CPAIO R, 2017, pp. 376–386

    2017

  17. [25]

    Hamann, B

    M. Hamann, B. Strasser, Graph bisection with pareto optimizat ion, Journal of Experimental Algorithmics (JEA) 23 (1) (2018) 1–2

    2018

  18. [26]

    Tamaki, Positive-instance driven dynamic programming for tr eewidth, in: Proc

    H. Tamaki, Positive-instance driven dynamic programming for tr eewidth, in: Proc. of ESA, 2017, pp. 68:1–68:13

    2017

  19. [27]

    Fischer, J

    E. Fischer, J. A. Makowsky, E. V. Ravve, Counting truth assig nments of formulas of bounded tree-width or clique-width, Discrete Applied Ma the- matics 156 (4) (2008) 511–529

    2008

  20. [28]

    Samer, S

    M. Samer, S. Szeider, Algorithms for propositional model coun ting, Journal of Discrete Algorithms 8 (1) (2010) 50–64

    2010

  21. [29]

    I. L. Markov, Y. Shi, Simulating quantum computation by contra cting tensor networks, SIAM Journal on Computing 38 (3) (2008) 963– 981. 25

    2008

  22. [30]

    de Oliveira Oliveira, On the satisfiability of quantum circuits of sm all treewidth, in: International Computer Science Symposium in Russia , Springer, 2015, pp

    M. de Oliveira Oliveira, On the satisfiability of quantum circuits of sm all treewidth, in: International Computer Science Symposium in Russia , Springer, 2015, pp. 157–172

    2015

  23. [31]

    E. F. Dumitrescu, A. L. Fisher, T. D. Goodrich, T. S. Humble, B. D. Sullivan, A. L. Wright, Benchmarking treewidth as a practical compo nent of tensor network simulations, PloS one 13 (12)

  24. [32]

    Grasedyck, Hierarchical singular value decomposition of ten sors, SIAM Journal on Matrix Analysis and Applications 31 (4) (2010) 2029–205 4

    L. Grasedyck, Hierarchical singular value decomposition of ten sors, SIAM Journal on Matrix Analysis and Applications 31 (4) (2010) 2029–205 4

    2010

  25. [33]

    T. Sang, P. Beame, H. Kautz, Heuristics for fast exact model counting, in: Proc. of SAT, 2005, pp. 226–240

    2005

  26. [34]

    Lagniez, P

    J.-M. Lagniez, P. Marquis, An improved decision-DNNF compiler, in : Proc. of IJCAI, 2017, pp. 667–673

    2017

  27. [35]

    Charwat, S

    G. Charwat, S. Woltran, Dynamic programming-based qbf solvin g., in: Proc. of SAT, 2016, pp. 27–40

    2016

  28. [36]

    J. K. Fichte, M. Hecher, M. Morak, S. Woltran, Answer set solv ing with bounded treewidth revisited, in: Proc. of LPNMR, Springer, 2017, pp. 132–145

    2017

  29. [37]

    P. D. Seymour, R. Thomas, Call routing and the ratcatcher, C ombinatorica 14 (2) (1994) 217–241

    1994

  30. [38]

    Robertson, P

    N. Robertson, P. D. Seymour, Graph minors. x. obstructions to tree- decomposition, Journal of Combinatorial Theory, Series B 52 (2) ( 1991) 153–190

    1991

  31. [39]

    Sasak, Comparing 17 graph parameters, Master’s thesis, T he University of Bergen (2010)

    R. Sasak, Comparing 17 graph parameters, Master’s thesis, T he University of Bergen (2010)

    2010

  32. [40]

    Swami, A

    A. Swami, A. Gupta, Optimization of large join queries, in: Proc. o f SIG- MOD, 1988, pp. 8–17

    1988

  33. [41]

    Dechter, Bucket elimination: A unifying framework for reaso ning, Arti- ficial Intelligence 113 (1-2) (1999) 41–85

    R. Dechter, Bucket elimination: A unifying framework for reaso ning, Arti- ficial Intelligence 113 (1-2) (1999) 41–85

    1999

  34. [42]

    J. D. Biamonte, S. R. Clark, D. Jaksch, Categorical tensor ne twork states, AIP Advances 1 (4) (2011) 042172

    2011

  35. [43]

    Chaudhuri, M

    S. Chaudhuri, M. Y. Vardi, Optimization of real conjunctive que ries, in: Proc. of PODS, 1993, pp. 59–70

    1993

  36. [44]

    Cavallo, M

    R. Cavallo, M. Pittarelli, The theory of probabilistic databases., in : Proc. of VLDB, 1987, pp. 1–4

    1987

  37. [45]

    NumPy, http://www.numpy.org/, Accessed: 2019-12-02. 26

    2019

  38. [46]

    Robeva, A

    E. Robeva, A. Seigal, Duality of graphical models and tensor net works, arXiv preprint arXiv:1710.01437

    arXiv

  39. [47]

    Abo Khamis, H

    M. Abo Khamis, H. Q. Ngo, A. Rudra, F AQ: questions asked freq uently, in: Proc. of PODS, ACM, 2016, pp. 13–28

    2016

  40. [48]

    C. L. Lawson, R. J. Hanson, D. R. Kincaid, F. T. Krogh, Basic line ar algebra subprograms for fortran usage, ACM Transactions on Ma thematical Software

  41. [49]

    Fatahalian, J

    K. Fatahalian, J. Sugerman, P. Hanrahan, Understanding the efficiency of gpu algorithms for matrix-matrix multiplication, in: Proc. of EURO- GRAPHICS, ACM, 2004, pp. 133–137

    2004

  42. [50]

    Due˜ nas-Osorio, M

    L. Due˜ nas-Osorio, M. Vardi, J. Rojo, Quantum-inspired boole an states for bounding engineering network reliability assessment, Structural S afety 75 (2018) 110–118

    2018

  43. [51]

    Evenbly, R

    G. Evenbly, R. N. Pfeifer, Improving the efficiency of variationa l tensor network algorithms, Physical Review B 89 (24) (2014) 245118

    2014

  44. [52]

    Dechter, Constraint processing, Morgan Kaufmann, 2003

    R. Dechter, Constraint processing, Morgan Kaufmann, 2003

    2003

  45. [53]

    Ying, Tensor network skeletonization, Multiscale Modeling & Sim ulation 15 (4) (2017) 1423–1447

    L. Ying, Tensor network skeletonization, Multiscale Modeling & Sim ulation 15 (4) (2017) 1423–1447

    2017

  46. [54]

    Q.-P. Gu, H. Tamaki, Optimal branch-decomposition of planar gr aphs in O(n3) time, ACM Transactions on Algorithms (TALG) 4 (3) (2008) 30

    2008

  47. [55]

    Dalmau, P

    V. Dalmau, P. G. Kolaitis, M. Y. Vardi, Constraint satisfaction, b ounded treewidth, and finite-variable logics, in: Proc. of CP, 2002, pp. 310 –326

    2002

  48. [56]

    K. Kask, R. Dechter, J. Larrosa, A. Dechter, Unifying tree d ecompositions for reasoning in graphical models, Artificial Intelligence 166 (1-2) ( 2005) 165–193

    2005

  49. [57]

    D. J. Harvey, D. R. Wood, The treewidth of line graphs, Journa l of Com- binatorial Theory, Series B 132 (2018) 157–179

    2018

  50. [58]

    `Alvarez, R

    C. `Alvarez, R. Cases, J. D ´ ıaz, J. Petit, M. Serna, Communication tre e problems, Theoretical computer science 381 (1-3) (2007) 197–2 17

    2007

  51. [59]

    I. L. Markov, Y. Shi, Constant-degree graph expansions tha t preserve treewidth, Algorithmica 59 (4) (2011) 461–470

    2011

  52. [60]

    Samer, S

    M. Samer, S. Szeider, Constraint satisfaction with bounded tr eewidth re- visited, Journal of Computer and System Sciences 76 (2) (2010) 1 03–114

    2010

  53. [61]

    de Oliveira Oliveira, Size-treewidth tradeoffs for circuits comp uting the element distinctness function, Theory of Computing Systems 62 (1 ) (2018) 136–161

    M. de Oliveira Oliveira, Size-treewidth tradeoffs for circuits comp uting the element distinctness function, Theory of Computing Systems 62 (1 ) (2018) 136–161. 27

    2018

  54. [62]

    Viger, M

    F. Viger, M. Latapy, Efficient and simple generation of random sim ple connected graphs with prescribed degree sequence, in: Proc. of COCOON, 2005, pp. 440–449

    2005

  55. [63]

    Lagniez, P

    J.-M. Lagniez, P. Marquis, Preprocessing for propositional mo del counting, in: Proc. of AAAI, 2014, pp. 2688–2694

    2014

  56. [64]

    Lagniez, E

    J.-M. Lagniez, E. Lonca, P. Marquis, Improving model counting by lever- aging definability., in: Proc. of IJCAI, 2016, pp. 751–757

    2016

  57. [65]

    J. K. Fichte, M. Hecher, S. Woltran, M. Zisser, Weighted model counting on the GPU by exploiting small treewidth, in: Proc. of ESA, 2018, pp. 28:1–28:16. 28 Appendix A. A Comparison of T reewidth and Carving Width In this section, we perform an experimental comparison of treew...

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.